Hat puzzle

From Wikipedia, the free encyclopedia
This article has multiple issues. Please help improve the article or discuss these issues on the talk page.

The hat puzzle is a classic logic problem, attributed to Todd Ebert, in his 1998 Ph.D. thesis at the University of California, Santa Barbara. It is a strategy question about a cooperative game, which has been shown to have connections to algebraic coding theory.

Contents

[edit] Question

A team of N players, where N is at least three, are randomly assigned hats that are equally likely to be white or black, under conditions such that:

  1. Each team player can see the hats of the other team members, but cannot see their own hat;
  2. Team members cannot communicate in any way.

Hypothetically, there are N prisoners, but as there was not enough space for all of them. The jailer decides to give them a test, and if all of them succeed in answering it, he will release them, whereas if any one of them answers incorrectly, then he will kill all of them. He describes the test as follows:

I will put a hat, either white or black, on the head of each of you. You can see others' hats, but you can't see your own hat. You are given 20 minutes. I will place at least one white hat and at least one black hat. All of you should tell me the colour of the hat on your head. You can't signal to others or give a hint or anything like that. You should say only WHITE or BLACK. You can go and discuss for a while now.

All of them go and discuss for some time. And after they come back, he starts the test. Interestingly, each of them answers correctly and hence all are released.

The question is, is there a pre-agreed team strategy for guessing, which will improve on an expected value of 0.5, for the score of the team, when it is awarded as 1 if there is at least one correct hat colour guess and no incorrect guess, and 0 otherwise?


[edit] Answer

The answer has been shown to be 'yes' for when N is 3, and some higher values of N.

There is a variation of the puzzle in which the players can answer 'I don't know' as a third choice. In this version there is no relevance in the order, or at what time the players give their answer. One strategy for solving this version of hat problem employs Hamming codes, which are commonly used to detect and correct errors in data transmission. Here, one can't solve the problem in the sense that the players will win in any case, but the probability for winning will be much higher than 50%, depending on the number of players in the puzzle configuration (e.g. winning probability of 87.5% for 7 players when using Hamming codes.)

This strategy can be applied to team sizes of N = 2k − 1 (e.g. 3, 7, 15) and achieves an expected value of \frac{2^k-1}{2^k}. Notably, the Hamming code strategy yields greater expected values for larger values of N.

For example, each prisoner counts the number of white hats and black hats they see, and waits for 10N seconds, where N is the lower of the two numbers. After that time, (providing the other prisoners are all doing the same thing), he must be wearing the hat of the colour which he is seeing fewer of.

  • Everyone wearing a white hat will see W − 1 white hats and B black hats.
  • Everyone wearing a black hat will see B − 1 black hats and W white hats.


  • If W < B then all white hats will say 'White' at the same time (10(W − 1) seconds), and everyone else knows they are wearing black.
  • If B < W then all black hats will say 'Black' at the same time (10(B − 1) seconds), and everyone else knows they are wearing white.
  • If W = B then all prisoners will know their colour at the same time. (10(B − 1) seconds, or 10(W − 1) seconds, they are equivalent).

[edit] Explanation

[edit] Four Prisoners

Suppose that there are 4 prisoners, among which two wear black hats and other two wear white.

          W        W                      W        W

                               or 

          W        B                      B        B

Now, the first one sees two black hats, and a white hat. Had he seen three black hats, he could have easily told that his hat is a white hat, since there should at least be one white hat. Same is true for the second person who is also wearing a white hat. So, all of them are in dilemma. After 10 seconds, each of them thinks that, since the others are not able to deduce their own hat colour, he must be wearing a white hat. So they say WHITE. At about the same time, by similarity, the other two persons say BLACK.

[edit] Six Prisoners

Consider that there are 6 prisoners, among which three wear black hats and other three wear white.

        W                            W                            W

 B             B             B              W              W             W

                      or                           or    

 B             B             B              B              B             B

        B                            B                            B

Now, the first one sees three black hats, and two white hats. Had he seen five black hats, he could have easily told that his hat is a white hat. Also, if he had seen 4 black hats, and a white hat, after 10 seconds, he could have guessed that he must be wearing a white hat since the other person wearing white hat is unable to deduce his hat's colour. (See Four Prisoners). But now he is still in dilemma and is unable to judge the colour even after 20 seconds. So, after 20 seconds, all the persons wearing white hats say WHITE and all the prisoners wearing black hats say BLACK.

[edit] See also