Prisoners and Hats

100 prisoners are given the following challenge: They will be taken to a room and will be arranged in a column, such that each of them faces the backs of the prisoners in front. After that, black and red hats will be placed on their heads, and the prisoners will be asked one at a time what is the color of their hat, starting from the one at the back of the column. If a prisoner guesses his color correctly, he is spared; if not – he is executed. If every prisoner can see only the hats of the prisoners in front of him in the line, what strategy should they come up with, so that their losses are minimized?

SOLUTION

There is a strategy which ensures that 99 prisoners are spared and there is 50% chance that one of them is executed. Clearly, one can not do better.

The strategy is as follows: The first prisoner (at the back of the line) counts the number of black hats worn by the prisoners in front. If the number is odd, he says “BLACK”. If the number is even, he says “RED”. Then, the second prisoner counts the black hats in front of him, figures out the color of his own hat, and answers the question.The third prisoner sees the number of black hats in front of him and uses this information, along with what the second prisoner’s hat is, to determine the color of his own hat. The prisoners continue in the same manner until all 99 prisoners in the front guess their hat colors correctly. The chance for survival of the first prisoner is 50%.

Unknown Author

We do not know where this puzzle originated from. If you have any information, please let us know via email.

Unknown Author

Puzzle Newsletter