The hat problem

Fremen

Three people walk into a room and have hats placed on their heads. Either a red or a green hat is placed on each person's head according to a fair coin toss. No-one can see what colour hat is on their own head.

After looking at each other's hats, they all have the option to guess what colour hat is on their head, or pass. If at least one person guesses correctly and no-one guesses wrong, they all split a cash prize between them.

Everyone guesses simultaneously, and no communication is allowed before guessing. What is their best strategy for guessing?
(They can do better than winning 50% of the time)

What is the best strategy in the general case, with N people playing the game?


I read about this in a new york times article which gave the solution. I'm kind of annoyed I read it because the solution to the three person problem is quite nice.

Michael Collins

How about this:

You look at the other peoples' hats. Now if you see two different hats, you pass, as you can't make an educated guess this way. If you see two hats the same (there will always be someone who can see this) you say the opposite colour to whatever two hats you see. In other words if you see two green hats, you say red. If you see two red hats, you say green.

So this way, as it's a fair coin toss, one of you will be right 6/8 = 3/4 of the time, and wrong the remaining quarter. So on average you'll be right 75% of the time...

Fremen

Nice one, that's the solution for the three-person game.

The solution to the general case is much more difficult, I haven't had time to look into it in any detail