# hat problem

The hat problem may be stated as follows: Three contestants, Alice, Bob, and Cedric, enter a room and a hat is placed
on each contestant's head so that he or she can't see it. The color of each
hat is based on a coin toss – blue (B) for heads, red (R) for tails.
After all the contestants enter the room, they look at the colors of the
others' hats and, based on this information, they guess the color of their
hat. They can guess red or blue, or, if they can't make up their mind, they
can pass. No communication is allowed during the competition, but the players
are allowed to agree on a strategy before play begins. The team wins if
at least one of them guesses correctly, and none of them guesses incorrectly.
What is the team's best strategy? At first sight, it may seem as if no effective
strategy is possible beyond each contestant guessing their own hat color.
In fact, this is the very worst approach since, to succeed, it requires
that everyone guess correctly and the probability of this is only 1/2 ×
1/2 × 1/2 = 1/8. A far better plan is for the contestants to agree
that two of them will pass while the third takes a stab at the color of
their own. Then the odds improve to one in two. Beyond this it is hard to
see any way that the probability of success could be increased. Yet there
is an even better strategy. The key to it is to realize that that there
are only two cases (RRR and BBB) where everyone's hat is the same color
but six cases where two hats are the same color and the other hat is a different
color (RRB, RBR, BRR, BBR, BRB, and RBB). This suggests the following strategy
for members of the team: *if you see two hats of opposite colors, pass.
If you see two hats of one color, guess that your hat is the other color*.
If everyone's hat is the same color, all players on the team will guess
wrongly and the team will lose. But the chance of this happening is only
2/8 (= 1/4). In every other possible case, the odd person out will guess
correctly and their team-mates will pass, so the team will win. This strategy
wins 6/8 (= 3/4) of the time – and can't be improved upon. Since half
of each player's guesses will be wrong, it's impossible to do better than
a strategy in which each player in turn guesses correctly alone three times
out of four, and the fourth time all guess wrongly.

What if there are more players in the team? Say the number of players is *n*. By the reasoning used described, it's clear that the team can't
hope to win more than *n*/(*n*+1) of the time. Yet it isn't
at all obvious that it can do this well. Having more people, it seems, might
make it harder for them to synchronize their wrong guesses. However, it
turns out that, if the number of people in the team is *one less than
a power of 2*, this best-possible value can be achieved. For example,
with a team of 7, the team can win 7/8 of the time, and with a team of 15,
they can win 15/16 of the time. The strategy involved is complicated but
is closely linked to Hamming codes, which are a method of encoding and transmitting
information so that, even if a small number of errors are made in transmission,
the original information can all be recovered. For teams of the others sizes,
such as nine, ten, or 13, mathematicians have yet to find an optimal strategy
or establish what proportion of the time the team can be expected to win.