The Line of Persons with Hats #2


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.


100 persons 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 only of those persons standing ahead of him in line. Each hat is one of $N$ possible colors, where these possible colors are known to the persons before they start strategizing.

Starting from the back of the line (that is, with the person who can see the hat colors of all of other 99 persons), 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 persons whose exclamation accurately describes their own hat color.

What strategy should the 100 persons use in order 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 persons 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 he has heard, the worst-case score is 1. If every other person exclaims the hat color of the person immediate in front and that person then repeats the color he has just heard, then the worst-case score is 50. Can you do better?

Solution     Reveal