When several players cooperate under uncertainty, the key is not always to talk more, but to agree in advance who should speak and who should remain silent.
Ebert's hats
Riddle statement
Three players randomly and independently receive a red or blue hat. Each can see the other two's hats, but not their own.
Before starting, you can agree on a plan. Then, all at once, each person must do exactly one of these three things: say “red”, say “blue” or be silent.
The group wins if these two conditions are met:
- at least one of the three says a color;
- No one who speaks is wrong about the color of their own hat.
What is the highest probability of success that can be guaranteed?
Show solution
Solution
Answer: the highest probability of success is $3/4$.
The strategy is this:
if a player sees two hats of the same color, he says that his is the opposite color;
if he sees two hats of different colors, he remains silent.
There are $2^3 = 8$ possible distributions of hats, all equally likely.
If the three hats are the same—all red or all blue—each player sees two identical hats and applies the rule: all three speak and all three fail. Those are the two lost cases.
In any other distribution there are two hats of one color and one of the other. The player wearing the minority color sees two identical hats, speaks and gets it right; The other two see different colors and remain silent. The group wins.
Therefore, the group wins in 6 of the 8 cases:
To see that it cannot be done better: the 8 cases are grouped into 4 complementary pairs, where all the colors are inverted. In both cases of each pair, players see exactly the same information but with the colors swapped. If in one of the two someone speaks, in the other they would speak with the same visual information and would make a mistake. This forces at least 2 missed cases, which is exactly what the previous strategy achieves.