A logician has a favorite game to play at parties. He shows a set of solidly colored stickers to all his logician friends. Each logician, without looking, puts a random sticker on his/her own back. Each logician can only see the stickers on other people's backs, and no one can look at the unused stickers. The logicians take turns announcing whether they can deduce their own color. The game ends when someone announces he/she can deduce his/her own color.

One time while playing this game, no one had yet ended the game even though everyone had a turn. Should they continue to take second turns, or should they just give up and start a new game? Prove that it is impossible for a game that hasn't ended after everyone's first turn to ever end, or provide a counterexample.

Answer: They should give up and start a new game, 
it is impossible for the game to end after the first 
round in this case.

Prove: Simple, they take turns announcing "I CAN deduce 
my color" or "I CANNOT deduce my color". Assuming that 
no one would answer "cannot" until they were sure of 
their inability to deduce their own color, and that 
the game only 'ends' when someone answers "can" 
independant of their guess or its accuracy!

Posted by michelle on 2005-04-11 06:22:51