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(3): armando by Tristan)

That's a good example. I haven't realized that the guess could be get from a chain of silences. So my solution fails.

Anyway, I think the example brings me closer to real solution.

It seems deduction works like that: the third logician thinks that, if he got red, the second logician would have been able to win, deducing he (the second) hasn't red because otherwise (if he would be wearing red) the first logician would have win.

Generalizing, it seems that the logician who guess make one hypotesis about his own color, and conclude it is not the color he is really wearing on the basis of a chain of silents of precedents logicians, pointing to the fact that otherwise the first logician of the chain (the head of the chain) would have guess.

But, if it's like that, a second round is to exclude. In the hypotesis of a second round the winner would be at the same time last ring and head of the chain of reasoning. Practically, he has to assume his own color as "data" to conclude what his color is, from that "data". But that is petitio principii (latin).

So, wouldn't be a real progress on second round.

Posted by armando on 2005-03-23 21:07:07