1000 Prisoners' problem
A thousand prisoners on the death row are offered a chance at freedom. They are asked to play the following game.
The prisoners would be lined up, in a single file, one in front of another and a cap, which could be white or black would be kept on each prisoners head. Thus, each prisoner would be able to see the caps on the heads of all those in front of him.
(i) Each prisoner has a single chance to utter a single word, the color of his cap. If it is right, the prisoner is set free. If it is wrong, he is shot dead.
(ii) All the prisoners can hear one another's words and can identify the person who said it, and know one another's position in the line.
Before the game is played. The 1000 prisoners are allowed a last chance to plan a strategy to maximize the number of acquittals.
What is the minimum number of people who would go free, if a good enough strategy is formulated.
The answer is 999.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
The best strategy :
The first prisoner says "White hat" if he sees an odd number of White hats and "Black hat" if he counts an even number of White hats in front of him.
The first prisoner has a 50% chance of freedom as his choice is uncorrelated to his hat's colour.
For i − t h prisoner, with i > 1 he will count the number of white hats in front of him, then add the number of times "White hat" was announced by the previous i − 1 prisoners. If the resultant number is odd, then the i − t h prisoner has a white hat, which he would announce and go free. If the sum was even, the prisoner will say "Black hat".
Thus, 999 of the prisoners can go free for sure. The first prisoner has 50% chance of freedom,