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.

I disagree with the below counterexamples.  I will not say why, for I don't want to solve my own problem.  Keep on trying!  I will post the solution when someone has solved this problem.

You may assume that all the logicians are perfectly logical.  You may not assume anything about the set of stickers used or the number of logicians.  That is the convention of these types of logic puzzles.  Logicians are just wierd like that.

When coming up with a counterexample, there is no need to have a general rule, like n logicians, r red stickers, b blue stickers, etc.  It suffices to give concrete numbers, like 4 logicians, 3 blue stickers, 2 red stickers, or something like that.  It is easier to see whether a counterexample works when you have actual numbers.

For the proof, if one exists, you must use general rules, and prove that there is no possible set of stickers and logicians that constitutes a counterexample.

Edited on March 19, 2005, 8:46 pm

Posted by Tristan on 2005-03-19 20:30:37