Three Hat Colors


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.


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