## Line of People with Hats #2

Source

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

I solved it and wrote up my solution.

Problem

100 people are standing in line, each facing the same way. Each person is wearing a hat, but the hat color is not known to the person wearing the hat. In fact, a person knows the hat color of only those people standing ahead of her in line. Each hat is one of $N$ possible colors, where these possible colors are known to the people before they start strategizing.

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 one of the $N$ colors. 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 the first 99 people exclaim 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 her and that person then repeats the color she has just heard, then the worst-case score is 50. Can you do better?

Solution