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.