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 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%.