|
If the following proof is perhaps not clear or detailed enough, you may look at Eddy Karat's proof, which is similar, but a lot clearer than mine.
The logicians should just give up and start a new game with a different set of stickers.
The set of stickers can be any combination of colors. For the sake of simplicity, let's call the color that appears most often red. It doesn't matter if there are other colors that appear just as often.
For a game to end, the number of non-red stickers must be less than the number of logicians playing. If there are more non-red stickers, then no one can possibly deduce his/her own color, nor extract any information from other logicians' announcements.
Assuming that this isn't the case, we can safely say there are X less non-red stickers than logicians. Note that among all the logicians, there must be at least X red stickers being worn.
Let's number the logicians in the order they take their turns. Logican 1 will deduce his color if he sees X-1 red stickers. If he did not deduce his own color, there must be at least X red stickers on the logicians after him.
Logician 2, knowing this, will deduce his color if there are X-1 red stickers on the logicians after him. If he did not deduce his color, there must be at least X red stickers on the logicians after him.
This pattern continues, but eventually one of the logicians must be able to deduce his color, when there are only X-1 logicians after him. This logician knows that he has a red sticker. Note that there are other ways for logicians to deduce their color, especially if there are other colors that appear just as often as red.
Therefore, whether a game ends or not is entirely dependent on the set of stickers given and the number of logicians. If the game does end, it will always end before anyone takes a second turn. |
