Line of People with Hats #1


I got this problem from Rustan Leino, who was told it by Ernie Cohen. A generalization of this problem is at the following link.

I solved it and wrote up my solution.


100 people are standing in line, each facing the same way. Each person is wearing a hat, either red or blue, but the hat color is not known to the person wearing the hat. In fact, a person knows the hat colors of only those people standing ahead of them in line.

Starting from the back of the line (that is, with the person who can see the hat colors of all other 99 people), in order, and ending with the person at the head of the line (that is, with the person who can see the hat color of no one), each person exclaims either "red" or "blue". These exclamations can be heard by all. Once everyone has spoken, a score is calculated, equal to the number of people whose exclamations accurately describe their own respective hat colors.

What strategy should the 100 people use to get as high a score as possible, regardless of how the hat colors are assigned? (That is, what strategy achieves the best worst-case score?)

For example, if everyone exclaims "red", the worst-case score is 0. If each of the first 99 people exclaims the color of the hat of the person at the head of the line and the person at the head of the line then exclaims the color she has repeatedly heard, the worst-case score is 1. If every other person exclaims the hat color of the person immediately in front of them and that person then repeats the color they've just heard, then the worst-case score is 50. Can you do better?

Solution     Reveal