There are 100 prisoners in a line, facing forward, one behind another. Each of them has either a white hat or a black hat on, which they cannot see themselves. The first prisoner in line can’t see anyone’s hat. The second prisoner can see only the first prisoner’s hat. The third prisoner can see only the first two prisoners’ hats, and so on, down to the 100th prisoner who can see all of the 99 hats in front of her. The executioner who is standing behind the 100th prisoner and says that he will release anyone who correctly guesses the color of their own hat. He will start by asking the 100th prisoner the color of their hat, and then he will ask the 99th prisoner the color of their hat, then the 98th, and so on. All the prisoners will hear all the other prisoners’ guesses. Keeping them in line, the executioner gives them some time to discuss tactics before he asks the 100th prisoner what the color of her hat is. They come up with a strategy that guarantees that 99 of them will survive. What is their strategy?
Their strategy is for the 100th prisoner to say “black” if she sees an even number of black hats in front of her and to say “white” if she sees an odd number of black hats in front of her. The 99th prisoner, upon hearing this and seeing the colors of the 98 hats in front of him, will be able to deduce the color of his own hat. The 98th prisoner, having heard what the 100th and 99th prisoners said and able to see 97 hats in front of him, will be able to deduce the color of his own hat, and so on. This strategy guarantees that (at least) 99 of the prisoners will survive.