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.

Counterexample: If there are n guests all with red stickers, and all m extra stickers are blue, the game will last m-1 rounds. On the m-1 round each player will be expecting everyone else to declare their color as red if his color is blue. When the first player still has to pass, everyone else knows they have red.

There are counterexamples. But the circumstances that allow them are very restricted. There are, in practice very few sticker sets that allow a counterexample. If the original set and number of guests do not allow counterexamples, the logicians would quit the game after the first round.

Posted by TomM on 2005-03-19 06:25:02