One hundred prisoners are lined up, facing one direction and assigned a random hat, either red or blue. Each prisoner can see the hats in front of them but not behind. Starting with the prisoner at the back of the line and moving forward, they must each, in turn, say only one word which must be "red" or "blue". If the word matches their hat color they are released, if not, they are kept imprisoned. They can hear each others' answers, no matter how far they are on the line, but they do not hear the verdict (whether the answer was correct). A friendly guard warns them one night before, giving them enough time to come up with a strategy. How many prisoners can be freed using the best strategy?
Look at the colors the last prisoner (the one at the back) sees in front of them: one color will appear an even number of times and the other an odd number of times. Beforehand the group agrees that the last prisoner will say the color he sees an odd number of times. That single announcement gives the group a shared reference to reason from.
After the last prisoner announces the color he saw an odd number of times, each later prisoner counts how many hats of that color they see ahead and how many times that color has already been said by people behind them. Comparing those two numbers tells them whether their own hat must be that color or the other color.
Solution
Answer: using the agreed odd/even announcement the group can guarantee that 99 prisoners are freed; only the first speaker (at the back) may be at risk.
Strategy
Beforehand, the prisoners agree that the last person in line (who speaks first) will look at the 99 hats in front of them and say the color that occurs an odd number of times among those hats. If both colors appear an even number of times (this cannot happen with 99 hats), they pick a convention, but with 99 hats one color must be odd.
The first speaker's announcement gives the group a shared reference: everyone now knows which color the last person saw an odd count of.
When it is a later prisoner's turn, they count how many hats of that announced color they see in front of them and also count how many times that color has already been spoken by prisoners behind them. If those two counts disagree with what the last prisoner announced (odd vs even), the prisoner deduces their own hat must be the announced color; otherwise it is the other color. Using this rule, every prisoner after the first can deduce their hat with certainty and say the correct color.
Why this works
The first announcement fixes whether the total number of the announced color among positions 2–100 is odd or even. Each correct declaration by a later prisoner effectively reveals their hat to everyone else and updates the running counts. Because everyone hears the announced colors and can see the hats ahead, they can always compare the expected odd/even value with the counts they observe and deduce their own hat. Only the initial speaker may be wrong because they have no prior announcement to compare against.
