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.

 <o:p></o:p>

I will try solution again but in the opposite sense (my precedent example fails).

 

Supposed each logician has seen the set of colored stickers before picking up them as the problem posted states, the game will come at an end only in two ways:<o:p></o:p>

  <o:p></o:p>

or<o:p></o:p>

1) because one player sees that all the set of colors except one are already placed in the back of the other logicians, and so he knows his color is precisely that excepted, and announced it <o:p></o:p>

or <o:p></o:p>

2) because he can exclude all the set of colors except one color - his own -, deducing from the silent of precedent logicians.<o:p></o:p>

 <o:p></o:p>

It's evident that if the game is finished in the first way the end occurs in the first round.<o:p></o:p>

 <o:p></o:p>

If the game finish in the second way it's the same thing. Reason:<o:p></o:p>

 <o:p></o:p>

One logician (logician A) can exclude a color on his own back (color R) when all the stickers of that color are on the back of other logicians, or when if that color (R) would be on his back, a precedent logician (logician B) would have found that all the stickers of that color (compressed logician's A one) have been picked up by logicians, and would have been able to finish the game himself (logician B). But if logician B was not able to finish the game it means that logician A isn't wearing a sticker of that color. <o:p></o:p>

 <o:p></o:p>

But this also means that logician B was (is) in the same situation of logician A; that is, for logician B, as A do not have on his back the excluded color and neither is it in the others logician's back, that color is also a real possibility (for him =B). So he, B, was (is) in the doubt about being himself wearing the color (color R) (but really he has not, and logician A knows it, in the same way logician B knows A isn't wearing it).<o:p></o:p>

 <o:p></o:p>

We are conduced at this conclusion: that the game will finish in the mood 2) only if there is a par of players (A and B) (or more pairs) which are in the same situation (with each one doubting for finishing the game between the color they really have on theirs own back and other common color). The silent of the first player of the pair will allow the second player to realized his color.<o:p></o:p>

But that means the game necessarily finish on the first round (at the second player pair's turn) or doesn't have finish. Second round is unuseful.

I think this is ok, but perhaps it can be said much more easier.

Posted by armando on 2005-03-20 14:36:31