At the other end of the spectrum are problems within every layman's grasp, such as the Monty Hall problem (which shall get its own post in short order, now that I've thought of it). The one I want to talk about today is the problem of hailstone sequences. As the linked page explains, these are called "hailstone sequences" because the sequences generated by the following algorithm go up and down like a hailstone in a cloud. Take any number - for the sake of the cited article, we'll call it n - and follow these steps:
1a. If n is even, divide it by two. n/2=n'1b. If n is odd, multiply it by three and add one. 3n+1=n'2. Repeat step 1 with n'. Lather, rinse, repeat ad infinitum.
OK, now eventually, your sequence is going to end up repeating at 4, 2, 1, 4, 2, 1... Go ahead, try it. I've got time. There's even a little applet on the page linked above.
All right, satisfied? Now I've got two propositions that I'm just going to lay out there:
1. Every number put through these steps will end up repeating at 4, 2, 1, 4, 2, 1...2. There is at least one number that does not end up at 4, 2, 1, 4, 2, 1...
Nobody - not one single person - has been able to prove either of these contradictory propositions. But one of them must be true! The common-sense approach is that any time you end up at a power of two (2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, etc.), it's Game Over, and you're eventually going to hit on a power of two, so there. This is also true of powers of two multiplied by any power of ten, since it will end up at a power of ten which all fall into the same old trap (though for slightly more subtle reasons). In fact, you could conceivably show that all non-prime numbers end up at 4, 2, 1, etc., though I'm a bit fuzzy on the how of the matter. You'd probably want to start by showing that all multiples of three will do it, then all multiples of five, then six, seven, eight, nine, etc. (1, 2, and 4 are skipped for what should be obvious reasons), until you identified a general solution. But that still leaves the problem of primes, and prime numbers are ipso facto numbers that don't fit any pattern - the sieve of Eratosthenes (which eliminates all non-prime or "composite" numbers until the square of the next prime) demonstrates this by eliminating all numbers generated by regular patterns, leaving you what's left: the primes. Because of this, a general solution to prove proposition 1 (above) may well be impossible.
Frustratingly, it may be an insoluble problem - proposition 1 may be true but unprovable, meaning that proposition 2 can never be proven and the question shall always remain open. This possibility could itself be proven by showing that proposition 1 can never be verified in a way that neither confirms nor refutes proposition 2. Whether this can even be done is also an open question, though.
So scratch your head in wonder at this interesting emergent property of numbers, and then have a beer. I'm sure going to!