Hats in a Line
100 red/blue hats, guess your own from the back. How many can you save for sure?
by MindYourPuzzle
A gorgeous "one clever bit saves almost everyone" puzzle.
100 people stand in a line, each wearing a hat that is either red or blue (assigned adversarially — someone who wants you to fail chose them). Each person can see the hats of everyone in front of them, but not their own and not those behind.
Starting from the back of the line (the person who sees all 99 others), each person in turn must say a single word — "red" or "blue" — guessing their own hat. Everyone hears every guess. A person is saved if their guess matches their actual hat.
They get to agree on a strategy beforehand, but once the guessing starts, the only information transmitted is the sequence of "red"/"blue" guesses everyone hears.
Using the best strategy, how many of the 100 can be guaranteed saved?
(Answer with the number.)