Prisoners with hats
30 prisoners will line up facing the same way and with a black or white hat on their head. They are not told how many hats there are of each colour. Each prisoner can only see the hats of those in front of him, but not his own or that hats behind him. A guard will ask each in turn, starting with the prisoner at the back of the line, the one who can see all the hats except his own, which colour their hat has. The prisoners can only answer ‘black’ or ‘white’. If they are right they are liberated, if not they are executed. Every prisoner can hear the answers to the other prisoners. The guard does not say who answered correctly until they all have answered.
Before the test starts the prisoners, who know the procedure of the test outlined above, are given time to discuss the best strategy they should follow to make sure that the maximum number of prisoners survice.
What is their best strategy? How many will survive?
The Royal Spanish Mathematics Society is 100 years old this year. The newspaper El País celebrates this with a math problem every week. The problem above is, in essence, one of them. Here is a video presenting the problem (in Spanish).
September 19th, 2011 at 1:15 pm
Here’s one strategy:
Every other prisoner calls out the color of the hat immediately in front of him, the next guy calls out that same color. The means AT LEAST 15 get it right and survive, the other 15 survive at random depending on whether they match the person in front of them.
September 19th, 2011 at 11:03 pm
Hah! I can do MUCH better.
Let the prisoners agree that the first declaration of a color from the prisoner at the back of the line is a code for even or odd, e.g. BLACK => ODD. He counts the number of black hats ahead of him, and announces whether that number is odd or even by stating “black” or “white.” He’s taking a chance, but setting everyone else up to go free.
Every subsequent prisoner can look at the hats ahead of him and determine whether there is an even or odd number of black hats remaining. If it’s odd, say “white” and all ahead make no adjustment. If it’s even, say “black” (you’re the oddball) and all ahead switch the count from odd to even. Repeat, revert as necessary.
29 prisoners go free, and the guy at the end of the line gets potluck.
September 20th, 2011 at 8:33 am
Mike, that’s really good news for the prisoners!