Prisoners & Hats

The Puzzle: 100 prisoners are standing in a line, all facing the same direction.

• Each prisoner wears a Black or White hat.
• A prisoner can see the hats of everyone in front of them, but not their own or those behind them.
• Starting from the back (who sees 99 hats), each prisoner must guess their hat color.
• If they guess correctly, they live. If wrong, they die.
• They can hear the guesses of the prisoners behind them. How many can they save with a pre-planned strategy?

1. The Strategy: Parity

They can save 99 prisoners for sure, and the 100th (the first to guess) has a 50% chance of living.

The Code:

• The first prisoner (at the back) counts the number of Black hats he see in front of him.
• If the count is EVEN, he says “Black”.
• If the count is ODD, he says “White”.
• (He may die, but he has just provided the “Parity Bit” for everyone else!)

The Deduction (Prisoner 99):

• Prisoner 99 knows the total parity (from Prisoner 100’s shout).
• He looks at the 98 hats in front of him.
• If the parity of what he sees matches the total parity, his own hat must be White. If it changed, his hat must be Black.
• The next prisoner does the same, but also considers the guesses already made behind him.

2. Example

• 3 Prisoners: (Back) B, W, B (Front)
• Prisoner 1 (Back) sees W and B. Count of Black = 1 (ODD). He says “White”.
• Prisoner 2 sees B. He knows the total Black count was ODD. Since he sees 1 Black, his own must be White (otherwise the total would be even). He says “White” (Lives!).
• Prisoner 3 knows the total was ODD. P2 said White. Total Black still ODD. He hears P2’s guess. He says “Black” (Lives!).

---

Interview-Focused Questions

Key Takeaway

This puzzle tests your ability to use cumulative state to derive individual values.