A Hundred Prisoners and Their Hats
The puzzle
A hundred prisoners are put in a line. Each is given a hat, red or black, in any proportion the jailer likes. Each prisoner can see every hat in front of them and none behind, including their own.
Starting from the back of the line, each must say one word - "red" or "black" - loud enough for everyone to hear. Guess your own hat colour correctly and you live; guess wrong and you do not. Nothing else may be communicated: no pauses, no tone, no signals.
They may agree a strategy the night before. 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 prisoner at the back can see all ninety-nine hats in front, and has no information at all about their own. Their word is therefore free to carry something else.
Hint 2
What single fact about ninety-nine hats would let the hundredth person deduce theirs, and then the next, and the next?
Show the answer Hide the answer
Ninety-nine for certain, and the hundredth with probability one half. The prisoner at the back announces the parity of the red hats they can see - "red" for an even number, "black" for odd - and everyone ahead tracks it.
How to get there
The prisoner at the back counts the red hats in front of them and says "red" if that count is even and "black" if it is odd. They have no way to know their own hat, so they are guessing - a one-in-two chance - but their word has told everyone else the parity of the ninety-nine hats ahead.
The ninety-ninth prisoner now counts the red hats they can see, which is ninety-eight of them. If that count has the parity just announced, their own hat is not red; if the parity differs, it is. Either way they know their colour exactly, and they say it.
Everybody further forward hears that answer, updates the running parity, and repeats the same deduction with one fewer hat in front. Each of the ninety-nine is certain.
The technique worth keeping
Parity is one bit that summarises any number of items, and it survives being updated one item at a time. That is what makes it the standard tool when a single broadcast has to inform a whole chain of people - each one subtracts what they have learned and passes the rest along.