Solution
One Hundred Hats
Show the problem again
100 prisoners stand in a line, each wearing a red or blue hat, seeing only the hats in front of them. From the back of the line forward, each must guess their own hat color aloud; correct guesses live. They may agree on a strategy beforehand. What is the maximum number of prisoners who can be guaranteed to survive?
Worked solution
The answer is 99 (the last-in-line survives with probability 1/2). The rearmost prisoner announces the parity of the red hats they see (e.g., "red" = odd count). Each subsequent prisoner counts the red hats visible ahead and, combined with all previous announcements, deduces their own color exactly. Everyone after the first is saved with certainty; the first prisoner's own hat is unknowable, so 99 is optimal.
Source: Classic hat-guessing puzzle in wide circulation; the parity strategy is standard in the literature. Statement written for AxiomIQ.