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.

The last person in queue says the color of the hat of the person in front.  He has 50/50 chance of survival.

The person in front of him, therefore, says the color of his/her own hat.  That person will always go free.

The third person says the color of the hat of the person in front of him.  He has 50/50 chance of survival.

The fourth person says the color of his own hat, so he goes free.

Using this strategy, EXACTLY 50% of the prisoners will ALWAYS go free...

...unless N=3 up until N<16.  At N=3 only one person is ensured freedom (the others are left to luck) and at N=16 is supposed to be where eight prisoners have a 50/50 chance, and according to statistics, eight occurrences of the same event, if the odds are 50/50 are very improbable.

There's a simpler way.  If N is large enough, the last guy could count the number of hats and colors, and guess his hat is the color who has the fewest...  Then people would know his color was the fewest in number so the next person counts as well, and if HE sees the last guy's color was STILL the fewest in number, he guesses the same color.  If it's not, he guesses the opposite... but if the number of hats are absolutely equal, he HAS to guess.

All the people should therefore COUNT the number of blue and red the people BEHIND them mention, so that when there are fewer in number, they can make the math with the colors that have been mentioned.

 

Posted by Alexis on 2006-07-16 03:37:22