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.

Each player can only end the game:

1) because he sees that all the colors except one are placed in the back of the logicians, and so he knows his color is that one,

or

2) because he is in doubt about just two colors and can deduced from the silent of a precedent logician that one of this two colors isn't in his back, (and so he has the other one).

After the first round passed with nobody knowing his own color the possibility 1) is irreversible down.

But not the possibility 2. The first logicien on second round can guess his own color if the silent of all the others means for him to exclude necesarily one color, leaving just another.

For example: four logicien, four blue stickers and four green ones. First logicien took green color and the other logiciens have blue. The first logicien see thre blue colors and he know that if he has blue in his back the second logicien will finish the game. But the second sees a green and two blues and he can't know his own color. So he can't announce. The same case is for the third and for the four logicien. As nobody stops the game, the first logicien knows on second round that his color is green.

Posted by armando on 2005-03-19 15:15:24