The Hats Problem | FractionRush

🎩 The Setup

Topics: parity, logic, binary strategy, optimisation

10 prisoners stand in a line, each wearing either a black or white hat. Each prisoner can see all hats in front of them, but cannot see their own hat or any hat behind them.

Starting from the back of the line, each prisoner must call out either "Black" or "White". If they correctly identify their own hat colour, they are freed. Otherwise, they remain imprisoned.

The prisoners may agree on a strategy beforehand — but once the hats are placed, no other communication is allowed.

Challenge: What strategy guarantees freeing at least 9 out of 10 prisoners?

🎩P10
(back)

🎩P9

🎩P8

🎩P7

🎩P6

🎩P5

🎩P4

🎩P3

🎩P2

🎩P1
(front)

Strategy: Agree beforehand that "Black" = the count of black hats is odd.

Prisoner 10 (back): Counts all 9 black hats visible ahead. If odd → calls "Black"; if even → calls "White". This encodes the parity. P10 has a 50% chance of being correct.

Prisoner 9: Heard P10's call (the parity). Counts the 8 black hats ahead of them. Uses the known parity to deduce whether their own hat is black or white. Always correct.

Each subsequent prisoner updates the running parity using all calls they've heard. Always correct.

Suppose hats are (back→front): B W B B W W B W B W

P10 sees 9 hats ahead: W B B W W B W B W → 4 black hats (even). Calls "White" (even parity). P10 actually has Black → P10 is wrong.

P9 sees 8 hats ahead: B B W W B W B W → 4 black. Heard parity = even. Sees 4 black ahead (even). Even parity already accounted for → their hat must be White. Correct ✓

Every subsequent prisoner uses the same logic: adjust parity by what they see and what was called.

📝 Questions

Prisoner 10 can see all 9 hats ahead. Can they know their own hat colour for certain? What is their probability of being correct if they guess randomly? 2 marks

Explain what "parity" means in this context. How does Prisoner 10 encode useful information into their single call? 3 marks

Prisoner 9 hears Prisoner 10 call "Black" (odd number of blacks ahead of P10). P9 looks ahead and counts 3 black hats. What colour is P9's hat? Show your reasoning. 3 marks

After P9 correctly calls "Black", Prisoner 8 looks ahead and counts 2 black hats. What colour is P8's hat? 3 marks

Using this strategy, what is the minimum number of prisoners guaranteed to be freed out of 10? What is the worst-case outcome? 2 marks

Extension: If hats could be one of 3 colours (Red, White, Blue), the parity trick doesn't directly work. Suggest how the strategy might be adapted for 3 colours using modular arithmetic. 7 marks

Answer Key

🎩 Hats Problem

1.No, P10 cannot know their hat colour. Random guess = 50% (1/2) probability of being correct.

2.Parity = whether a count is odd or even. P10 encodes "total blacks ahead is odd/even" into their call. Everyone else can use this shared parity to calculate their own hat using information they have (hats they see + calls they hear).

3.P10 called "Black" = odd number of blacks total. P9 sees 3 black ahead (odd). If P9's hat is Black, total blacks ahead of P10 = 3+1=4 (even) — contradiction. So P9's hat must be White (3+0=3, odd ✓).

4.Running parity after P10 (odd) and P9 called Black (adding 1): updated parity = even. P8 sees 2 black ahead (even). Even parity needed and 2 ahead already even → P8's hat is White.

5.Minimum guaranteed freed = 9 out of 10. Worst case: P10 guesses wrong (1 incorrect), everyone else is correct (9 freed).

6.Assign Red=0, White=1, Blue=2. P10 calls the colour whose value makes the sum of all hat values ≡ 0 (mod 3). Each subsequent prisoner computes the required value mod 3. This guarantees all except P10 are correct.

🎩 The Hats Problem

Answer Key

🎩 Hats Problem

Answer Key

Hats Problem