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 of the ones in front. After that, black and red hats will be put on their heads, and the prisoners will be asked one at a time what is their hat color, 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 hat colors of the prisoners in front of him in the line, what strategy should they come up with, so that their losses are minimized?

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 the following: The first prisoner (at the back of the line) counts the number of black hats of the prisoners in front and says BLACK if the number is odd and RED if the number is even. Then the second prisoner counts the number of black hats in front of him, figures out whether his hat is black or white, and announces its color. The third prisoner counts the number of black hats in front of him and knowing what the second prisoner’s hat is, figures out what color his own hat is. 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%.

+ latest posts

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

Puzzle Newsletter

Subscribe to our newsletter and get our selected puzzles directly in your mailbox.


Responses

Your email address will not be published. Required fields are marked *

  1. I think the first person in the line that has 50% chance can also be saved. He just listen and count the hat from all of the prisoner. Then he will also know which is he’s wearing. I’m I right?

    And Serife is right about the hat has to be equal in number, or being told before the game has started. I will explain to you, If I can see 99 person in front of me and seeing 49 black, 50 white; how do you know your own hat if the hat is (may not) being equal. It can be 49 black and 51 white.

  2. For this strategy to work, it has to be known that there is an equal number of black and red hats.

    1. Hello Serife. Why do you think that this condition is necessary? The strategy seems to work no matter what the numbers of red and black hats are.