Could You Solve This $1 Million Hat Trick?

Nov. 29, 2002 -- 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

There is, in fact, a strategy that enables the group to win 75 percent of the time. It requires each one of the three to inspect the hat colors of the other two and, if the colors are the same, then to guess his or her own hat to be the opposite color. When any one of the three sees that the hat colors of the other two differ, then he or she must remain silent and not make a guess.

A listing of all possible hat colors for the three helps to see why this strategy works. The eight possibilities for the hat colors of the three people are RRR, RRB, RBR, BRR, BBR, BRB, RBB, and BBB, the first entry indicating all three wearing red hats; the second indicating the first two wearing red and the third one wearing blue; the third indicating the first and third wearing red and second wearing blue; and so on.

In six of the eight possibilities (in bold type), exactly two of the three people have the same color hat. In these six cases, both of these people would remain silent (why?), but the remaining person, seeing the same hat color on the other two, would guess the opposite color for his or her own hat and be right. In two of the eight possibilities (in italics), all three have the same color hat and so each of the three would guess that their hats were the opposite color and all three of them would be wrong.

So when they're wrong, they're very wrong, but when they're right, they're just right enough.

If one were to run this game repeatedly, the number of right and wrong guesses would be equal even though the group as a whole would win the money six out of eight times or 75 percent of the time. That is, half of all individual guesses are wrong, but three-fourths of the group responses are right!

Generalizations?

Generalizations to situations with more than three people exist, but all solutions depend on finding a strategy that most of the time results in no one being wrong and every once in a while has everyone being wrong. With seven people playing, a strategy can be devised that wins the money 7/8ths of the time, with 15 players, 15/16ths of the time.

Are there other situations, say in the stock market, where independent pieces of information are provided to members of a group who can easily become aware of others' information but not of their own and, hence, where such strategies might work?

The idea behind these strategies can be phrased in terms of error-correcting codes, which are used in compact discs, modems, cell phones, and a host of other electronic devices. Not unrelated is the digit at the end of a bar code, a check digit which is (the units digit in) the sum of all the previous digit in the bar code.

P.S. Use As a Hoax?

Finally, it occurs to me that, were I so inclined, I could exploit the puzzle to appeal to gullible people desperate to find "evidence" for psychic phenomena.

After muttering a few incomprehensible New Age platitudes, I could describe the outcomes as a result of the three people attempting to mentally transmit hat colors and could further claim that whoever receives a strong enough signal from the others will speak up. Then I could observe that 3/4ths of the groups respond correctly and attribute this to their telepathic abilities.

Furthermore, by instructing my three co-conspirators not to follow the guessing rules strictly, I could further muddy the waters and inspire speculation about why people more often respond correctly when both of the other two are wearing the same color hat.

Professor of mathematics at Temple University and adjunct professor of journalism at Columbia University, John Allen Paulos is the author of several best-selling books, including Innumeracy and A Mathematician Reads the Newspaper. His Who’s Counting? column on ABCNEWS.com appears every month.