One hundred hats in a line
One hundred people stand in a line, one behind the other, all facing forward. Each wears a red or a blue hat. Each person sees the hats of everyone in front of them, but not their own hat and not the hats behind them.
Starting from the back of the line, each person in turn says one word, “red” or “blue”, and everyone hears it. A person is saved if the word they say is the colour of their own hat. The group agrees on a strategy before the hats are put on.
How many people can be saved for certain, whatever the hats are?
Fractions, decimals with at least 3 significant digits, and expressions such as sqrt(2)/2, e^-1 or pi/4.
The person at the back has no information at all about their own hat, so they cannot be guaranteed. Can everyone else be?
The person at the back can use their word to pass on one bit of information about the 99 hats they see.
h
s Shown after a correct answer. Revealing it first marks the problem as seen, not solved.
Idea. The person at the back sacrifices themselves to announce the parity of the red hats they see. With that one bit, and with every later answer, each person can work out their own colour.
The strategy. The person at the back counts the red hats in front of them and says “red” if the count is odd, “blue” if it is even.
Why it works. Take the next person. They know the parity of the red hats among the 99 people in front of the back person, which includes their own hat. They see all those hats except their own. If the number of red hats they see has the same parity as announced, their own hat is blue; otherwise it is red. They say it, and they are right.
Every later person does the same: they know the announced parity, they have heard the correct colours of everyone between the back and themselves, and they see everyone in front. The only unknown hat in the count is their own, so the parity fixes it.
Answer. Everyone except the person at the back is saved: 99. The person at the back is saved only if the parity happens to match their own hat, a 50% chance. No strategy can guarantee them, since nobody has given them any information when they speak. So 99 is the most that can be guaranteed.
A variant. With hats in 10 colours, number the colours 0 to 9; the person at the back announces the sum of the numbers they see modulo 10, and again 99 are saved.