All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > Logic
The logician's favorite game (Posted on 2005-03-18) Difficulty: 3 of 5
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.

  Submitted by Tristan    
Rating: 3.2500 (4 votes)
Solution: (Hide)
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.

Comments: ( You must be logged in to post comments.)
  Subject Author Date
re: Proof:Tristan2005-04-16 04:54:50
No SubjectEddy Karat2005-04-16 01:36:29
SolutionProof:Eddy Karat2005-04-16 01:31:55
QuestionProof:Eddy Karat2005-04-16 01:29:42
Unsolved stillTristan2005-04-15 02:39:05
Solutiona solutionmichelle2005-04-11 06:22:51
re: THE ANWSER...Tristan2005-04-08 22:06:55
THE ANWSER...Brandon2005-04-08 20:01:49
No SubjectBrandon2005-04-08 19:57:04
dependsFroggie2005-03-24 00:05:34
Would this round be possible?starlitsky2005-03-23 23:11:07
re(4): armandoarmando2005-03-23 21:07:07
re(3): armandoTristan2005-03-22 23:57:47
re(2): armandoarmando2005-03-22 08:12:14
re: armandoTristan2005-03-22 00:53:33
re: What I have to tell aboutarmando2005-03-21 15:43:55
What I have to tell aboutpcbouhid2005-03-21 12:42:42
traying solution againarmando2005-03-20 14:55:30
traying solution againarmando2005-03-20 14:36:31
Hints/TipsKeep on goingTristan2005-03-19 20:30:37
solution?armando2005-03-19 15:15:24
Some Thoughtsmaybe i'm just being sillystarlitsky2005-03-19 14:20:54
Some ThoughtsSeeing redTomM2005-03-19 06:25:02
re: Notes and ClarificationsTristan2005-03-19 02:21:48
Notes and ClarificationsGamer2005-03-18 19:48:53
helpdavid2005-03-18 19:22:41
clarificationiamkobe2005-03-18 14:09:45
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (6)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2024 by Animus Pactum Consulting. All rights reserved. Privacy Information