Hat puzzle

From Wikipedia, the free encyclopedia

The hat puzzle is a classic logic problem.

Contents 1 Question 2 Hint 3 Answer 4 Explanation 4.1 Four Prisoners 4.2 Six Prisoners

[edit] Question

There are 100 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 and even if 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 hat on your head. You can't signal to others or give 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 correct and hence all are released. How ?

[edit] Hint

Breakup the problem into puzzle of 2 prisoners, 3 prisoners and so on. And keep in mind that you are not the only one to think the solution.. there are other prisoners too.

[edit] Answer

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.