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.

(In reply to re: armando by Tristan)

Yes, my poor english doesn't help... Here I try to explain only the main point, doing it as simple as I can.

Logicians A, B, C, D, ...Z,  speaking also in this order.

Logician N sees that all the colors are on the back of other logicians except color R and color B.

Suppose logician N can exclude that he is wearing color R, deducing it from the silent of a precedent logicien (logicien M). He then realize that he is wearing color B and end the game at his turn.

What I tried to prove is that if N is able to exclude color B from the silent of M, M would be able to esclude color B from the silent of N, and he also (M) would be able to finish the game. Who of the both ends really the game depends only of who has his turn lately. If turns would begin from Z to A instead of A to Z, M would end the game taking profit of the silent of N.

But that means or game ends on the firts round or it doesn't end.

 

Posted by armando on 2005-03-22 08:12:14