One Hundred Hats in a Line

Question

100 prisoners stand in a line, each wearing a red or blue hat assigned adversarially. Each sees every hat in front of them, none behind, not their own. From the back of the line forward, each must say a single word, "red" or "blue," heard by all; those who name their own hat color are freed. The team strategizes beforehand. How many can be guaranteed freed?

Accepted Answer

99 guaranteed (and the back prisoner survives a coin-flip 50%). Strategy, broadcast a parity check. The back prisoner (100) announces "red" iff the number of red hats they see among the 99 ahead is odd. Each later prisoner maintains the running parity: prisoner k knows (a) the announced parity of hats 1–99, (b) the true hats of prisoners 99 down to k+1, each of them has already spoken and, by induction, spoken correctly, and (c) the hats they see ahead. XOR-ing (a), (b), (c) isolates their own hat exactly, so prisoners 99 down to 1 are all correct. Simulation over random hat assignments confirms: 99 correct every time, 100 right half the time. Why 99 is optimal: nobody sees hat 100, and 100 speaks first, their statement is a function of the other hats only, so an adversary fixes everyone else's hats, looks at what 100 will say, and colors hat 100 the opposite. No strategy saves all 100 with certainty. The concept: sacrifice one agent's payoff to transmit a checksum, then everyone error-corrects locally, literally a parity bit, the simplest error-detecting code. The discipline in execution is that every prisoner must track all prior answers; one lost bit desynchronizes the entire ch

One Hundred Hats in a Line

Problem

Your answer

Hints

More Brainteasers & Logic to train on