Ten Hats in a Line
The puzzle
Ten prisoners stand in a line, each wearing a black or white hat. Everybody sees every hat in front of them and none behind. Starting from the back, each says one word - "black" or "white" - and is freed if it names their own hat.
They may agree a plan beforehand but not communicate afterwards. How many can they guarantee to save?
Stuck?
One at a time, smallest first. Open only as many as you need — the whole point of the puzzle is the part you work out yourself.
Hint 1
The one at the back can see everything and will never know their own hat. Use their word for something else.
Hint 2
Count the black hats in front of you. What single fact would let everybody deduce their own?
Show the answer Hide the answer
Nine for certain, and the tenth with probability one half.
How to get there
Agree that the back prisoner says "black" if they see an even number of black hats and "white" if odd. That word is a parity, not a guess, so they have a coin-flip chance themselves.
The next prisoner counts the black hats they can see. Comparing that count’s parity with the announced one tells them their own hat exactly.
Each prisoner afterwards hears every guess made behind them and sees everything in front, so they can update the parity and deduce their own hat. Nine are certain.
The technique worth keeping
One bit of shared information can coordinate an arbitrary number of people. Parity is the usual bit to send because everybody can recompute it from what they see, and each new answer updates it.