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

©2020 K.R.M. Leino - Split Template by One Page Love