Could You Solve This $1 Million Hat Trick?

Nov. 29 -- A simple new puzzle has been tormenting mathematicians and computer scientists since Dr. Todd Ebert, a computer science professor at the University of California-Irvine, introduced it in his Ph.D. thesis in 1998.

Taken up more recently by Peter Winkler of Bell Labs and other puzzle mavens throughout the country, it has become the subject of discussion at high-tech companies, science chat rooms, and university math and computer science departments, in part because of its applications to so-called error-correcting codes.

The Puzzle

Here's the situation. Three people enter a room sequentially and a red or a blue hat is placed on each of their heads depending upon whether a coin lands heads or tails.

Once in the room, they can see the hat color of each of the other two people but not their own hat color. They can't communicate with each other in any way, but each has the option of guessing the color of his or her own hat. If at least one person guesses right and no one guesses wrong, they'll each win a million dollars. If no one guesses correctly or at least one person guesses wrong, they win nothing.

The three people are allowed to confer about a possible strategy before entering the room, however. They may decide, for example, that only one designated person will guess his own hat color and the other two will remain silent, a strategy that will result in a 50 percent chance of winning the money. Can they come up with a strategy that works more frequently?

Most observers think that this is impossible because the hat colors are independent of each other and none of the three people can learn anything about his or her hat color by looking at the hat colors of the others. Any guess is as likely to be wrong as right.

Is there a strategy the group can follow that results in its winning the money more than 50 percent of the time? The solution and a discussion are below, but you might want to think about the problem before reading on.

The Solution