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.

I do not know if this strategy is the best, but I shall assume the prisoners are only able to answer the warden's question in a normal tone "Red hat" or "Blue hat".

As the first prisioner will not be given any indication the color of his hat, whatever color he says will only give him a 50% chance of avoiding the alligators.  He can, however, offer a 100% chance of survival to the two prisoners in front of him.  If the two prisoners have like colored hats, he can say "Red hat", and if they have different colored hats he can say "Blue hat".  The next prisoner can then know the color of his own hat by knowing the color of the prisoner in front of him; and, when he calls out the color of the hat he has deduced his own to be, the prisoner in front of him will be able to deduce his own hat color.  This pattern can work for every set of 3 prisoners.  If the last set of prisoners is two, then the backmost prisoner of that set can simply identify the color of the hat of the prisoner in front of him. This will give N prisoners, where N is greater than 1, an average survival rate of at least 75% (around 83%, if N/3 is modulo zero).

If the prisoners were able to alter their tones, like having ability to say RED/BLUE and HAT in either high pitch or low pitch. The  information the first person can provide to the prisoners in front of him can give them a 100% survival rate.  Only the first person risks a 50% chance of being an alligator appetizer.

Depending upon the color of the prisoner's own hat, he can alter the tones to inform the (minimum) two prisoners ahead of him the color of their hat, and do this without compromising his own ability to correctly call out the color of his own hat. An example of this would be, if he knew his own hat were red, he could just call out his hat color. An alternating high-low pitch, "^red_HAT", could be used to tell the individuals in front of him that their hats are the same color; and a low-high pitch, "_RED^hat", could provide those two ahead that their hats are different in color. Each prisoner can use this technique to inform the two prisoners ahead.  

Edited on July 15, 2006, 1:08 pm

Posted by Dej Mar on 2006-07-15 11:31:29