Source

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.

Problem

100 persons 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 color only of those persons standing ahead of him in line.

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 either "red" or "blue". 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.

Each person keeps a running count of how many "red" exclamations she's heard. When it's her turn, she adds this running count to the number of red hats she sees in front of her. If this sum is odd, she exclaims "red"; otherwise, she exclaims "blue".

We'll call the first person the *announcer* because
her 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.

For any predicate $\mathsf{Pred}$, we define $I(\mathsf{Pred})$ to be the indicator variable for $\mathsf{Pred}$, i.e., 1 if $\mathsf{Pred}$ is true and 0 if $\mathsf{Pred}$ is false. The announcer will announce $I(\mbox{The number of winners' red hats is odd})$. We'll call this value the parity.

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

We start with the base case, the first winner to exclaim. Her running count is just the parity, based on the announcer's exclamation. To this she adds the number of red hats in front of her; since all other winners are in front of her, this is the number of other winners' red hats. So, the sum she computes $s$ is equal to the number of winners' red hats besides her own, plus the parity. In other words, $s$ is the number of winners' red hats, minus $I(\mbox{Her hat is red})$, plus the parity. The parity is congruent to the number of winner's red hats modulo 2, so adding these two values together gives 0 modulo 2. Thus, $s \equiv I(\mbox{Her hat is red}) \pmod 2$. In other words, her sum is odd if and only if her hat is red. Thus, she will correctly exclaim her hat color.

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, her running count will be the parity, from the announcer's exclamation, plus the count of the number of winners behind her with red hats. So, the sum she computes $s$ is equal to the number of winners' red hats besides her own, plus the parity. By the same reasoning as in the base case, we find that $s \equiv I(\mbox{Her hat is red}) \pmod 2$, and so her guess is correct.

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$