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

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 they've heard. When it's their turn, they add this running count to the number of red hats they see in front of them. If this sum is odd, they exclaim "red"; otherwise, they exclaim "blue".

We'll call the first person the *announcer* because
their role is to announce useful information.
We'll call the remaining 99 people the *winners* because
each of them will correctly exclaim their 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 their hat color.

We start with the base case, the first winner to exclaim. Their running count is just the parity, based on the announcer's exclamation. To this they add the number of red hats in front of them; since all other winners are in front of them, this is the number of other winners' red hats. So, the sum $s$ they compute is equal to the number of winners' red hats besides their own, plus the parity. In other words, $s$ is the number of winners' red hats, minus $I(\mbox{Their hat is red})$, plus the parity. The parity is congruent to the number of winners' red hats modulo 2, so adding these two values together gives 0 modulo 2. Thus, $s \equiv I(\mbox{Their hat is red}) \pmod 2$. In other words, their sum is odd if and only if their hat is red. Thus, they will correctly exclaim their 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, their running count will be the parity, from the announcer's exclamation, plus the count of the number of winners behind them with red hats. So, the sum $s$ they compute is equal to the number of winners' red hats besides their own, plus the parity. By the same reasoning as in the base case, we find that $s \equiv I(\mbox{Their hat is red}) \pmod 2$, and so their 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$