Source

I got this problem from Rustan Leino, who thinks he got it from Lyle Ramshaw, who Rustan thinks got it from some collection of problems or maybe the American Mathematical Monthly.

I solved it and wrote up my solution.

Problem

A team of three people decide on a strategy for playing the following game. Each player walks into a room. On the way in, a fair coin is tossed for each player, deciding that player's hat color, either red or blue. Each player can see the hat colors of the other two players, but cannot see her own hat color. After inspecting each other's hat colors, each player decides on a response, one of: "I have a red hat", "I have a blue hat", or "I pass". The responses are recorded, but the responses are not shared until every player has recorded her response. The team wins if at least one player responds with a color and every color response correctly describes the hat color of the player making the response. In other words, the team loses if either everyone responds with "I pass" or someone responds with a color that is different from her hat color.

What strategy should one use to maximize the team's expected chance of winning?

For example, one possible strategy is to single out one of the three players. This player will respond "I have a red hat" and the others will respond "I pass". The expected chance of winning with this strategy is 50%. Can you do better? Provide a better strategy or prove that no better strategy exists.

Solution
Reveal

Each player, if she sees that her two partners have the same color hat, responds with a guess of the other color. Otherwise, she passes.

This strategy wins with probability 3/4. After all, if all players' hat colors are the same, they will all guess wrong and lose. However, in all other cases two of the players' hat colors will match and the other one will be the only one to respond and will do so correctly. Thus, the probability of losing is the probability of all hat colors being identical, which is 1/4.

Let's number the three players 1, 2, and 3. We'll define
a *configuration* as a list of three hat colors corresponding to those
players' hat colors in order, e.g., "red, blue, red". We say two
configurations are *adjacent* if they differ in exactly one position. For
instance, "red, blue, red" is adjacent to "red, blue, blue" because they
differ in the last position. A consequence is that each configuration has
exactly three adjacent configurations.

We first observe that for any strategy, any winning configuration for that strategy is adjacent to at least one losing configuration for that strategy. Here's why. A configuration can only win if one of the players responds; call that player $i$. Now, consider the adjacent configuration that differs only in position $i$. From player $i$'s perspective, no hat color is different, so $i$ will make the same response as in the winning configuration. However, in this new configuration this response will be wrong.

Our strategy has six winning configurations out of a possible eight. So if a strategy beats our strategy, it must have at least seven winning configurations. It clearly can't have eight winning configurations, because then it would have no losing configurations but our observation says that any winning configuration must have a losing configuration. So it must have exactly seven winning configurations and one losing configuration. However, this also isn't possible, since here every winning configuration would have to be adjacent to the sole losing configuration, but that losing configuration can only be adjacent to three configurations, which is much less than seven.

Thus, there is no better strategy and ours is optimal.