A group of prisoners is under sentence of death and the warder decides to give them a test to gain their freedom. He tells them, "I will place a red or blue hat on each of your heads and then I'm going to arrange you in random order in a row so that no prisoner will be able to see his own hat but each one will see all the hats in front of him. Starting with the guy at the back each of you in turn must loudly say what color hat you think you have. Correct answers will go free, incorrect ones will be thrown to the alligators in the moat. I will give you time for a brief meeting before we start, so you can plan your optimum strategy."
What strategy can the prisoners - there are N of them - adopt to improve their odds above 50:50?
Hint: They need to agree on a strategy which allows each person to identify his/her own hat while simultaneously providing as much information as possible for all those in front.
Do the I find out whether the prisoners behind me are right or wrong, before I have to choose?
Here are some strategies that occur to me:
(1) If I don't know my hat color, name the hat color of the prisoner in
front of me. All the even numbered prisoners go free, and the
odd-number ones have a 50-50 guess.
or
(2) If
there are an odd number of prisoners, then the last prisoner says Blue
if he see the same number of red and blue hats ahead of him, and Red
otherwise. If he can say Blue (equal colors ahead), then all the
prisoners ahead of him can figure out their hat colors and go
free. If he says Red, then this still gives some information
which may help the next person. This approach certainly improves
the prisoner's chances, and it needs more work, but it is not
clear where it figures to be a higher percentage than approach
1. It is certainly better if there are only three
prisoners. With three prisoners, the first to name has a 50/50
chance, and the other two go free.
Edited on July 15, 2006, 11:07 am
Thoughts. (Spoiler?) Question.
