The hundred prisoners with hats

Chance and uncertaintyLevel 4 · Advanced · ●●●●○

There are 100 prisoners in line. They randomly put a blue or red hat on each one.

Each prisoner can see the hats of everyone in front of him, but not his own or those behind him. Starting with the last person in the line (who sees 99 hats), each one must say out loud 'blue' or 'red'.

If he guesses the color of his hat correctly, he is saved. They can come up with a strategy beforehand.

What is the maximum number of prisoners that can guarantee being saved and what is the strategy that allows them to achieve it?

Solve this riddle

Hints

Show hints

Result: 99 prisoners can be guaranteed to survive.
Key idea: the last prisoner sends one bit of information (parity of blue hats).
For each next prisoner (P99 to P1), combine seen hats and previous answers to preserve that parity.

Solution

Show full solution

Answer: 99 prisoners can be guaranteed to survive.
Parity strategy:

Before the game, everyone agrees that P100 will encode the parity of blue hats among P1..P99.
P100 says 'blue' if the number is even, 'red' if it is odd.
Each next prisoner (P99 down to P1) uses:

the announced parity,
the hats they can still see ahead,
and the already spoken colors,

to deduce their own hat color uniquely.
P100 may fail, but every other prisoner can infer their color with certainty.

Related riddles

Keep practicing

If you enjoyed this one, try more pure-logic riddles, explore this theme, browse the full archive, or read the riddle-solving guide.

← Previous: The hundred numbered boxes · Next: The light bulb room →