# HatProblem

If you think that there's no new mathematics under the sun, consider the recently discovered "Hat Problem":

A team of three people are put into a room together. A hat, either red or blue, is placed on each. You can't see the color of your own hat, only the colors of the other two people's hats. No communication is allowed among teammates once they get their hats. After seeing the other hats, the three of you are separated and each is asked "What is the color of your hat?" You can answer "red" or "blue", or you can abstain from replying. If at least one person on the team guesses the right answer and nobody guesses wrong, then your team wins.

The challenge for the team: agree, before you go into the room, on a strategy that will maximize your chance of success.

How in the world can you possibly do better than 50%? None of you knows anything about your own hat, and you can't communicate. At best, it seems, you could conspire in advance to let one team member guess (a 50-50 gamble) and the other two abstain. If more than one of you guesses, the odds only get worse.

Or so it seems. But there is a way to do better --- in fact, to increase your chance of victory to 75%! Think about it for a while if you would like to figure it out for yourself (or if you're like me and can't solve the puzzle, read about it elsewhere). It's a clever, honest, totally counterintuitive method. It's extensible to more people and more complex problems. And the winning strategy is intimately related to ideas from information and coding theory.

That's part of the magic of mathematics: it unveils truth, independent of our common-sense prejudices.

More than a decade ago a simpler puzzle akin to the Hat Problem swept across the world. It was called "The Three Doors" and similarly challenged orthodoxy. In brief:

Three closed doors are in front of you. You must pick one to open. Behind two of the doors are goats (and you don't like goats). Behind the other door is a nice car (which you will get if you choose that door). You select one of the doors and then --- before your door is opened --- your host (who knows where the car is) opens one of the remaining two doors and shows you a goat behind it. Now do you stick with the door you initially chose, or do you change to the third still-closed door?

Again, think about it; the answer is rather counter-intuitive. I remember arguing with some of my colleagues about it and even writing a tiny computer simulation to persuade them when they wouldn't believe me. The right strategy is clearer if you change the number of doors from three to a million (behind 999,999 of which are goats), and postulate that after you pick one door your host opens 999,998 of them, showing you all but one of the goats. Now do you stick or switch?

TopicScience - TopicPersonalHistory - TopicThinking - 2003-07-26

(correlates: StagesOfCredibility, TooManyMeetings, SolublesInsolubles, ...)