The Hat Problem

One hardy group of theoretical computer scientists stayed up late one rum-soaked night, playing a drinking game based on the following puzzle:

The hat problem goes like this:

Three players enter a room and a red or blue hat is placed on each person's head. The color of each hat is determined by a coin toss, with the outcome of one coin toss having no effect on the others. Each person can see the other players' hats but not his own.

No communication of any sort is allowed, except for an initial strategy session before the game begins. Once they have had a chance to look at the other hats, the players must simultaneously guess the color of their own hats or pass. The group shares a hypothetical $3 million prize if at least one player guesses correctly and no players guess incorrectly.

The same game can be played with any number of players. The general problem is to find a strategy for the group that maximizes its chances of winning the prize.

One obvious strategy for the players, for instance, would be for one player to always guess "red" while the other players pass. This would give the group a 50 percent chance of winning the prize. Can the group do better?

{snip}


Dr. Berlekamp, a coding theory expert, said he figured out the solution to the simplest case in about half an hour, but he saw the coding theory connection only while he was falling asleep that night.

"If you look at old things that you know from a different angle, sometimes you can't see them," he said.

The first thing Dr. Berlekamp saw was that in the three-player case, it is possible for the group to win three- fourths of the time.

Three-fourths of the time, two of the players will have hats of the same color and the third player's hat will be the opposite color. The group can win every time this happens by using the following strategy: Once the game starts, each player looks at the other two players' hats. If the two hats are different colors, he passes. If they are the same color, the player guesses his own hat is the opposite color.

This way, every time the hat colors are distributed two and one, one player will guess correctly and the others will pass, and the group will win the game. When all the hats are the same color, however, all three players will guess incorrectly and the group will lose.