Check out the blue-eyed islanders puzzle - a seemingly simple problem with a surprising solution:

WordPress - TerryTao - The blue-eyed islanders puzzle, 5 February, 2008
http://terrytao.wordpress.com/2008/02/05/the-blue-eyed-islanders-puzzle/

a slightly reworded version of problem can be found here:

http://xkcd.com/blue_eyes.html

with this abbreviated explanation of the solution:

http://xkcd.com/solution.html

Warning: thinking about this problem and its implications may hurt your brain! So you thought you knew what "common knowledge" is, eh? Also see this:

http://en.wikipedia.org/wiki/Common_knowledge_(logic)