The hat line
100 prisoners stand in a line, each wearing a black or white hat. Each can see every hat in front of them, but not their own or any behind. Starting from the back, each prisoner says one word, "black" or "white", which everyone hears. Anyone who names their own hat colour correctly goes free.
They can agree on a plan beforehand. How many can they guarantee to save?
Show hint
The person at the back has no information about their own hat, so they cannot be guaranteed. Can their one word tell everyone else enough?
Show solution
99.
The person at the back says "black" if they see an odd number of black hats in front of them, and "white" if even. That is a parity bit. The next person counts the black hats they can see; if the parity has changed, their own hat must be black. Everyone after keeps track of the parity and of the answers they have heard, so each can work out their own colour.
The back person survives only by luck (50%). The same parity idea is used in RAID storage and error-detecting codes.
Want a problem like this every day? See today's problem and keep a streak going.