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.

There are two types of this kind of problem, and they are quite different.<br><br>1) once each logician picks up his sticker (or disc, or whatever), he could only try to guess the colour of his own sticker <b>when it's his turn to guess</b>.<br><br>2)once each logician picks up his sticker, the winner will be the <b>FIRST</b> to guess the colour of his own sticker.<br><br>In the second type, the most common, each logician may conduct his reasoning <b>TAKING INTO ACCOUNT WHY THE OTHERS COULDN'T GUESS THEIR OWN COLOURS</b>, and can, them, deduce the colour of his own.<br><br>To clarify what I'm saying in the second case, think about of this situation : 3 logicians, to whom was showed 3 red stickers and 2 white stickers, and the three logicians picked up (without knowing, of course), the three red ones.<br><br>If they are asked <b>IN TURN</b>, no one will be able to deduce the colour of his own, because each one is seeing 2 red stickers, always.<br><br>But, if it is told them that the winner will be the <b>FIRST</b> to deduce his own colour, <b>each one</b> could reason like this :<br><br>"I'm (A) seeing two red stickers. If I have one white sticker, the other two (B and C) could deduce that none of them could have a white sticker, because if it happens, B (or C) will reason : I'm seeing a white sticker in A, and since C (or B) didn't announce at once his colour, my sticker could only be  red". And reasoning like this, all of the three logicians could deduce their own colour, in the same time (assuming they are equally logicals).<br><br>Therefore, if they are talking IN TURN (the first case), I see no change in the initial "status", and the game could end, without a second turn.   

 

Posted by pcbouhid on 2005-03-21 12:42:42