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?

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

Can a prisoner refuse to say anything and be shot to death? :-)

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

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.

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