I recently came across this really interesting puzzle:

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.

The most obvious solution gives you a 50% chance of winning. But interestingly enough, the best strategy gives you a chance of winning greater than 50%. (at least in the 3-hat case)

I won’t tell you any more details about the problem, because I don’t want to spoil your fun, but let’s just say that if you can solve the 7-person version, you’re well ahead of vast majority of mathematicians.

I solved the general case at 2 o’clock in the morning, when I was trying to get to sleep. I jumped out of my bed (without shouting “Eureka!”, unfortunately :p), turned on my computer and hacked together a quick Python program to check what probability of winning the best strategy gives you for 99 hats. I won’t tell you here what it is though. (If you really want to know, you can e-mail me at vlad@leedsmathgeeks.com).

Happy hat-problem-thingy-solving!

1. shAdOwArt Says:
   May 6th, 2009 at 4:03 pm

   Will the players recognize each other while playing the game? This is relevant to whether “player X should look at the color of player Y’s hat, and then guess” strategies are allowed.

2. Vlad Says:
   May 6th, 2009 at 5:25 pm

   @shadowart:
   Yes, that’s allowed.

3. John Halvorsen Says:
   September 14th, 2009 at 1:05 pm

   The solution is extremely simple.
   No matter how many people are in the room, all but three pass.
   Then at least two of them are guaranteed to have the same hat color – one person who sees the same color then passes.
   The remaining two people then know they are wearing the same color hat and both say the color of the hat on the other’s head. They win 100% of the time.

4. Vlad Says:
   September 14th, 2009 at 8:03 pm

   @John:

   That’s a pretty cool solution.

   But the way the problem is set, they have to answer simultaneously. So no waiting for the one guy to pass

5. Livvloooo Says:
   October 22nd, 2009 at 10:05 pm

   Nice.