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 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

First, we'll present a strategy. Then, we'll prove that its worst-case score is 99 and that this is optimal.

While strategizing, the persons should decide on an assignment of the numbers $0$ through $N-1$ to the colors. In the following, when we speak of performing a mathematical operation on a color or a hat, we mean performing it on the number assigned to that color or the number assigned to the color of that hat. All additions and subtractions are performed modulo $N$, so all numbers wind up being between $0$ and $N-1$. Thus, we can talk about numbers as if they were colors; for instance, when we say that someone exclaims a number we mean she exclaims the color that number is assigned to.

We'll call the first person the *announcer* because
his role is to announce useful information.
We'll call the remaining 99 persons the *winners* because
each of them will correctly exclaim her hat color.

The announcer adds up the hats he sees and exclaims that sum. Each winner keeps a running sum of the other winners' announcements. When it's time for her to guess, she adds to this running sum the sum of the hats in front of her, then subtracts the result from what the announcer said. She exclaims this difference.

We prove by induction that each winner correctly guesses her hat color.

We start with the base case, the first winner to exclaim. Her running sum is zero, and to this she adds all the winners' hats besides her own, because she can see all other winners' hats. Thus, the result of subtracting this sum from the sum of all winners' hats is her own hat's color. So, she'll guess correctly.

For the inductive step, we assume that all winners so far have correctly guessed and it's time for the next winner to guess. In this case, the winner who's about to guess has a running sum equal to the sum of all winners' hats behind her. To this, she adds the sum of all winners' hats in front of her, obtaining the sum of all winners' hats besides her own. She subtracts this from the sum of all winners' hats, with the result being her own hat's color. So, she'll guess correctly.

By induction, the supposition is true for all winners, so the score is at least the number of winners, 99. This is the best worst-case score that can be hoped for, because no person knows anything about the first person's hat. Thus, the strategy is optimal. $\Box$