The Hat Problem

This is taken from http://dailynews.yahoo.com/h/nyt/20010409/tc/ why_mathematicians_now_c...

You might want to work on the problem first and then go to the web site to read the rest. Considering how popular the article says the puzzle is now, I don't understand why I haven't seen it mentioned here yet. Maybe it was already posted and I missed it.

Since the colours are independant, then without cheating this would seem to be the best you can do. If more than one person quesses you would be reducing your chances of winning, and no information can be gleaned from the other hat

Partial spoiler after original puzzle

Yes. A group of three (and hence any larger group) can win the prize 3/4 of the time.

Label the players A, B, and C. If A sees that the hats of the other two are the same color, she guesses that color; otherwise she passes. If B sees that A and C have hats of different colors, she guesses the color of A's hat; otherwise she passes. If C sees that A and B have hats of different colors, she guesses the color of A's hat; otherwise she passes. This wins the prize unless A's hat is red and B's and C's are blue, or vice versa.

This is clearly the maximum for three players: for the group to win at least 3/4 of the time, there must be at least one player who guesses right at least 1/4 of the time, and that player must also guess wrong at least 1/4 of the time.

As the article indicates, this is a difficult problem. Here's the answer:

They can win the prize six times out of eight. There are two strategies. Let the players be named Fred, Jim, and Sheila.

In the first strategy, they all apply the same rule: if someone sees two hats the same colour, they guess the opposite colour. Otherwise they pass. The possibilities are:

hats guess F J S F J S result

(Semi)-Spoiler space

A shorter solution is for each player to agree to look at the other two hats. If those hats are the same color, the player will guess the opposite color, but will otherwise remain silent. Then they win unless all hats are red or all hats are blue. Of course, this is no better than your solution.

Are they allowed to keep trying as long as they all pass, or do they get a at most one additional try? If the former, it's easy for them to get 7/8 probability of winning: on the first round, guess blue if you see two red hats, otherwise pass; on the second round, guess blue if you see one read hat, otherwise pass; on the third round, always guess blue.

If the latter, I don't see how they can do better than 3/4.

[partial spoiler space]

Your proof sketch seems good, but you need to rule out the possibility of a probabilistic strategy (e.g. someone guessing red with probability 0<p<1 if everyone else has red, and passing otherwise). From the little exploring I've done, this doesn't seem to give any improvement, but I'm not sure how you would prove it.

The optimum solution for general N is not known, although it is known when N < 9 (and when N + 1 is a power of 2, as your post pointed out).

Any probablistic strategy is a combination of deterministic strategies, each of which has a certain chance of being followed. Thus the chance of success with a probablistic strategy is a (weighted) average of chances of success with deterministic strategies, which means that at least one of the deterministic strategies must have a higher (or equal) chance of success than the probablistic strategy. Thus there exists a deterministic strategy which is optimal.

The only point of a probablistic strategy is if you have an opponent who is in some way trying to out-guess you. If your opponents actions do not depend on yours, you might as well go with a deterministic strategy.

Do you have a site with the solutions for N<9 ?

This is a cool puzzle.

You didn't. I saw it for the first time in Tuesday's NYT's, and if other people hadn't started posting, I would have posted it myself.

I'm afraid not. I got my info from the URL given by Mr. Kiley, which says that solutions are known for N < 9, but not what they are. It does say that the solutions are derived from binary codes. In fact, the entire problem is closely connected to coding theory, which is why mathematicians are so interested in it.

Yes, it is.

: improve further?

Adam Stephanides has already solved this problem for three people. This solution can be extended for any number of people to win with probability 1-1/2^n in at most n rounds as follows.

This is clearly an optimal probability but I don't know if it is an optimal number of rounds.

Spoiler:

. . . . . . . . . . . . . . . . . . . . . . . .

Designate one person as the 'guru' (in honor of a related problem, which many will recognize). If the guru sees no blue hats she should guess at random on the first round. Otherwise any player who sees exactly n blue hats (ignoring the guru's hat) should guess that their own hat is blue in round n+2.

Jonathan Dushoff