Solution to: Is my hat black or white?
General solution and asymptotic limit
There are N = 2n-1 people who are offered a challenge. If they win, they each get a million dollars. The men are blindfolded, and white or black hats chosen randomly are placed on their heads. The blindfolds are removed so they can each see the color of the hats on the other N-1. They must either guess the color of the hat on their heads or pass. If all pass, they lose. If one gets it wrong, they lose. If the answers are either pass or correct, with at least one correct, they win. What is the probability they will win a million dollars each? (Problem and Solution from Rutgers mathematics Professor Siddhartha Sahi, one of the original founders of the science club in Princeton and a colleague and friend of Gyan’s).
Solution: Let us illustrate the idea with N = 22-1 = 3. The answer is that they will guess correctly ¾ th of the time. We describe a method which generalizes to any number of hats of the form N = 2n – 1. We label each person with a binary label using n bits. For n=2, person 1 has label 01, person 2 has label 10 and person 3 has label 11. Their identifier “ab” corresponds to a vector (a,b) in a 2-d binary space in which vectors are added component-wise using the XOR rule: 1+1=0, 0+1=1=1+0 and 0+0 = 0.
Here is the rule for how they should guess:
When they open their eyes, each person adds up the vector ids of the people he sees wearing white hats using the XOR rule. If this sum is S = 00, he guesses that he is wearing white. If the sum is his own id, he guesses that he is wearing black, otherwise he passes.
The number of ways the hats can be distributed is shown in the Table above. If the hats are all black (one case), the sum each of them sees is S = 00 and they will all guess white (incorrect). When all hats are white, the sum will equal the id of each and they will all guess black (incorrect). This corresponds to two configurations. In all other cases, they will guess correctly. For example, if the hats are W,W,B, then persons 1,2 will see a white hat with ids 01 and 10 respectively. So, in this case, they will pass. Person 3 will see white hats with ids 01 and 10 which add up to his id 11 so he will say black.
What is the general strategy? Everyone adds the ids of the people with white hats. If that sum is zero, they guess white. If the sum equals their id they guess black.
It is instructive to see how this works out for N = 23-1 = 7. Now each person gets a binary code of 3 digits from 001 to 111 and uses rule described above. There are 8 possible configurations with 0,1,2,3,4,5,6,7 white hats and the number of cases for these are 1,7,21,35,35,21,7,1 respectively. The total number of configurations are 27 = 128. We will consider each case one by one.
a. If all hats are black (1 configurations), each sees S = 000 and all guess white which is incorrect.
b. If there is one white hat (7 configurations), then the one with the white hat will compute S=000 and guess white. The others will see one white hat which has an id not equal to theirs so they will each pass. Thus, we have 7 configurations and 7 correct guesses.
c. If there are two white hats there are 21 cases. Let us say the white hats are ids 001 and 010. They will compute 010 and 001 respectively which is not their id so they will pass. The ones with the black hats will see both white hats and compute S = 011. Hence the one with this id will say correctly say he has a black hat The others will pass. So, we will have 21 configurations and 21 correct guesses.
d. For the case of 3 white hats, there are 35 configurations of which there are 7 with S = 000 where all will guess incorrectly. These correspond to (001,010,011), (001, 100, 101), (001, 110, 111), (010, 100, 110), (010, 101, 111), (011, 100, 111), (011, 110, 101). In this situation, the ones with the white hats will guess black because the sum of the ids of the other two add up to their own. Similarly, the ones with black hats will see S = 000 and guess white. Thus, out of 35 configurations, there will be 7 incorrect guesses and 28 correct guesses.
e. With four white hats (7 configurations out of 35), it is easy to see that there are 7 configurations with S = 000. These are: (001,010,100,110), (001,010,101,111),(001,011,100, 110), (001,011, 101,111), (010,011,100,111), (101,011,101,110), (100,101,110,111). In these cases, everyone with a white hat will guess black and everyone with a black hat will guess white. For the rest of the configurations, there will be one person with a white hat who will see the sum of white hat ids add up to 000 and correctly guess white. The ones with black hats will pass. This case will have 7 incorrect guesses and 28 correct ones.
f. With five white hats, it is again easy to see that someone with a white hat will see S=000 for the sum of the other four and correctly guess white. The ones with the black hats will pass. This gives 21 correct guesses.
g. In the case with 6 white hats the sum of ids will add up to the id of the person with a black hat who will guess black. The rest will pass.
h. Finally, for 7 white hats, they will all incorrectly guess black since the sum of the ids of the white hats will add up to their own.
Hence, from the 1, 7, 21, 35, 35, 21, 7,1 possible configurations, there are 16 configurations where S is 000 and for these 16 , they will all guess incorrectly. Since the total number of cases is 27=128, the probability of success is (128-16)/128 = 7/8.
What is the optimum strategy with N not of the required form? In this case, it is best to use only the number of players that correspond to the strategy for the closest lower value of N where N is of the correct form and ask the remaining players to always pass. Thus, for N = 4,5,6, only three should play and the remaining should always pass.
It is easy to see that for any value of n, the number of cases when S is all zeros is 2N-n out of 2N cases. Hence the probability to guess correctly is p(n,N) = 1- 2N-n/2N = 1 – 1/2n = N/(N+1). For n = 2, N=3 we have is p(2,3) = ¾. And for n = 3, N = 7, p(3,7) = 7/8. It is a curious fact that the probability to guess correctly grows with the number of people and asymptotically reaches 1 for large n.
