Google Answers Logo
View Question
 
Q: colored hats puzzle ( No Answer,   5 Comments )
Question  
Subject: colored hats puzzle
Category: Science > Math
Asked by: racecar-ga
List Price: $5.00
Posted: 04 Aug 2003 14:55 PDT
Expires: 08 Aug 2003 13:15 PDT
Question ID: 240017
The puzzle:

The prison guard informs the prisoners that tomorrow they will play a
game.  The prisoners will be lined up, single file, so each can see
all the prisoners in front of him, but none of those behind him.  A
small hat, either blue, green, or red, will then be placed on each
prisoner's head, and the guard, starting at the back of the line, will
ask each man in turn to state the color of the hat on his head.  If the
prisoner answers correctly, he is freed, but otherwise he is shot on
the spot.  The prisoners have a day to plan a strategy for saving the
maximum number of lives.  What's the best they can do?

Cheesy solutions aren't allowed: each prisoner must say "blue",
"green", or "red" only, and varying the way the color is said (volume,
speed, etc.) as a way of codifying information is out; no mirrors, no
peeking; there can be any number of each color of hat--no assumptions
may be made about the probability distribution of colors.

I have a solution in which at most two prisoners die: 

The last prisoner in line says "blue" if the number of blue hats he
sees, not including the guy right in front of him (the second-to-last
in line), is even, and "green" if the number of blue hats is odd.  The
second-to-last prisoner then uses a similar code to let the rest of
the prisoners know whether the number of green hats he sees is even or
odd.  The third-to-last prisoner can then count the number of blue and
green hats he sees.  If both have the same parity as that seen by the
first two prisoners, then his hat is red, but if the parity of one of
the two colors is different, then his hat is that color.  Once he
hears the third guy's color, the fourth guy can do a similar
calculation to get his hat color, and so on all the way to the front
of the line.

My question:

A friend of mine claims to have a solution in which only at most one
prisoner dies, but he won't tell me what it is.  Does such a solution
exist?

I am not offering a large question fee, so I assume if this question
is answered, it will either be by someone who is familiar with the
puzzle, or who enjoys this type of puzzle enough that poor pay isn't
an issue.

Clarification of Question by racecar-ga on 07 Aug 2003 18:01 PDT
It seems like it shouldn't be that hard to either find a solution or
prove one doesn't exist.  Each possiblity has seemed almost within
reach as I've pondered this puzzle, but both have escaped me so far.

Mathtalk, not biting?
Answer  
There is no answer at this time.

Comments  
Subject: Re: colored hats puzzle
From: mvguy-ga on 04 Aug 2003 15:34 PDT
 
The mathematics of this type of puzzle (although not this one
specifically) are discusssed in this document:
http://www.hpl.hp.com/infotheory/hats_extsum.pdf
Subject: Re: colored hats puzzle
From: secret901-ga on 04 Aug 2003 16:53 PDT
 
Can a prisoner refuse to say anything and be shot to death? :-)
Subject: Re: colored hats puzzle
From: lynnspry-ga on 04 Aug 2003 22:40 PDT
 
Actually, your friend is correct, there is a solution where only one
prisoner will have a 1 in 3 chance of dying.  This solution lies in
summing the "point value" of each hat color and dividing that by the
number of hats then coding the "color" to match the remainder.  Of
course, the first prisoner has to work on luck alone.

Please check the link below for the full details of the solution
below.
http://www.stanford.edu/~cpetriuc/puzzles_wSolutions.html
Subject: Re: colored hats puzzle
From: racecar-ga on 05 Aug 2003 08:37 PDT
 
Hi secret,

I thought of that, and if that's allowed, it is a solution, because
there are four possible even-odd combinations for any two of the
colors.  So the first guy could assign one color to even-even, one to
even-odd, one to odd-even, and one to odd-odd.  The parity of the
third color then follows from the total number of prisoners, and only
the first guy needs to risk death.  I hope this is not the answer,
because it is cheesy.  I think if the first prisoner refused to
answer, the game would be off, and all the prisoners would be shot.

lynnspry--

thanks for the link. the solution there is essentially the same as the
one I gave above though, and for three colors, two prisoners must risk
death, each with a two-thirds chance of dying.
Subject: Re: colored hats puzzle
From: eek-ga on 08 Aug 2003 05:46 PDT
 
lynnspry's solution does work for three hat colors.  For example:
If I am the second prisoner from the back of the line, I will hear
either 0, 1, or 2 from the last prisoner depending on the sum of the
hat colors mod 3 (remainder after division by 3).  I can then find the
sum of that hats I see mod 3.  I will come up with 0, 1, or 2.  I can
then calculate the difference.  For example:  If I hear 1 and I count
2, then 1 - 2 = -1 = 2 mod 3.  My hat is whatever color corresponds to
2.  The person in front of me can then use this information to
calulate his hat color.  The result is that only one person must die
with probability 2/3 (two out of three hat color are wrong).

Explained sufficiently?
Bradley

Important Disclaimer: Answers and comments provided on Google Answers are general information, and are not intended to substitute for informed professional medical, psychiatric, psychological, tax, legal, investment, accounting, or other professional advice. Google does not endorse, and expressly disclaims liability for any product, manufacturer, distributor, service or service provider mentioned or any opinion expressed in answers or comments. Please read carefully the Google Answers Terms of Service.

If you feel that you have found inappropriate content, please let us know by emailing us at answers-support@google.com with the question ID listed above. Thank you.
Search Google Answers for
Google Answers  


Google Home - Answers FAQ - Terms of Service - Privacy Policy