They hear one letter, then each must guess. How do they save almost everyone? From the free puzzle set on Think Fanny — next try Three switches, one bulb.
The puzzle
One hundred prisoners stand in a single-file line. Each gets a black or white hat at random. Every prisoner can see all the hats in front of them, but not their own or any behind.
Starting from the back of the line, each prisoner must say either “black” or “white”. Everyone hears every guess. They may plan a strategy before the hats are placed, but not after.
How can they guarantee that 99 prisoners are saved, with only the back prisoner at risk?
Answer
The back prisoner says "black" or "white" as parity of black hats they see. Everyone else uses that shared parity bit.
Agree beforehand that the rear person sacrifices a 50/50 guess to encode the parity of black hats. Each later prisoner updates the running parity from what they see and hear.
