[I think I got this puzzle from Lyle Ramshaw, who I think got it from some collection of problems or maybe the American Mathematical Monthly.]

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

[Here’s a related problem, which I got from Jim Saxe.]

In this variation, the responses are different. Instead of "red", "blue", "pass", a response is now an integer, indicating a bet on having the hat color red. Once the responses have been collected, the team’s score is calculated as follows: Add the integer responses for those players wearing red hats, and subtract from that the integers of those players wearing blue hats. For example, if the three players respond with 12, -2, -100 while wearing blue, red, blue, respectively, then the team’s score is (-2) - (12) - (-100) = 90. The team wins if and only if its score is strictly positive.

For example, any strategy used in the first game can be used with this second game by replacing "I have a red hat" with 1, "I have a blue hat" with -1, and "I pass with 0". Such a strategy wins anytime the strategy would have produced a win in the first game; plus, this strategy may win in some cases where the strategy would not produce a win in the first game. For example, for hat colors red, red, red, the strategy "red", "red", "blue" loses in the first game, whereas 1, 1, -1 still wins in the second game. Hence, playing this second game can only increase the team’s expected chance of winning.

[Further generalizations.]

Of course, you can generalize these two problems from 3 players to N players. The solution to the first problem with N players may require more mathematical sophistication than the solution to the second problem with N players.