Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Four men in hats

I encountered the four men in hats puzzle for the first time today. My question is about a realisation I (think I) had while arriving at the solution, but I have no idea whether I've made a mistake somewhere.

Before I got to the actual answer, I was thinking about each man's chances of correctly guessing his hat colour. My thought process went something along these lines:

  • At first blush, D has the best chances, as he can see the most.
  • Hang on - D has only a 1 in 2 chance, the same as anyone else.
  • Anyone else? No - C can see that B has a white hat, so he knows there's only one other. It can be on one of three heads, so if he guesses that his own is black, his chances of being right are 2 in 3.

What threw me about this, assuming that last realisation isn't flawed in some way, is that D can also see that B has a white hat. Somehow, C has a better chance of being right, even though D (in some sense) has more knowledge, at least for this configuration of hats.

What am I missing?

UPDATE

Thanks for the answers so far. I don't think I was very clear on what I was asking though: I did manage to solve the puzzle, but what confused me was the realisation I outlined above while getting there. Forgetting the original goal of the puzzle (how do the men reason about the solution) and only taking into consideration their chances of successfully guessing, how do I explain the fact that C's chances seem better than D's, even though D can see everything that C can, and more?

share|improve this question
1  
interesting question. I hope you don't mind my edit, to the effect that the puzzle image and text have been inserted right to this page, directly accessible. Feel free to roll-back my edit! –  amWhy Jun 24 '11 at 22:50
    
Thanks amWhy; probably a good idea to insert the image. I've added it to the question using your link. –  shambulator Jun 27 '11 at 19:09
add comment

5 Answers

up vote 5 down vote accepted

D's chances of guessing correctly are either 100% (if B and C match) or 50% (if B and C mismatch). The chance that B and C match is 1/3, so D's overall chance of guessing correctly is 2/3.

C's chances of guessing correctly are 2/3 regardless of the initial setup.

Therefore D has the same chance as C.

Note: I'm assuming that all ${4 \choose 2} = 6$ initial set-ups are equiprobable.


Expanded Explanation:

There are 6 possible initial set-ups. Let's use lowercase for white and UPPERCASE for black. So initially we have one of these:

abCD aBcD aBCd AbCd ABcd AbcD

Note that only the third and sixth possibilities (in bold) have B and C matching.

Now consider D's strategy: if B and C match, guess the opposite (100% chance to be right). If not, guess at random (50% chance to be right). So D is right with probability (1)1/3 + (.5)2/3 = 2/3.

Now consider C's strategy: just guess the opposite of B no matter what. From the table above (and from your question), C's chance is 2/3.

Note: D can achieve the 2/3 chance of winning by just using C's strategy (which is simpler): just guess the opposite of C. As you can see from the table above, this wins 2/3 of the time too since it implicitly incorporates the bold cases.

share|improve this answer
    
+1 Nice job! Again, my post isn't an effort to out do either you or Steven: I simply thought it would be great to have a self-contained problem, to complement answers/explanations, and I felt awkward doing so within the OPs post. –  amWhy Jun 24 '11 at 23:00
    
Some great answers here! I've picked yours as the solution because it got to the heart of what I suspected I was missing: enumerating all the cases made it obvious that D in fact has just as good a chance, though it didn't seem that way at first. Though I have to keep Steven's answer in mind so as not to leap to any unwarranted conclusions... –  shambulator Jun 27 '11 at 19:42
add comment

(One caveat: I'm going to presume that the puzzle is to be solved specifically for the configuration of hats specified in the picture that you link to.)

What you're missing in this puzzle is the meta-knowledge; C doesn't know the color of D's hat, but he presumably knows that D is an intelligent reasoner. This means that if D doesn't call out an answer, then he doesn't know an answer. But if C's hat were the same color as B's, then D would be able to divine the color of his hat quickly; since he can see two hats of one color and knows there are only two hats of each color, then D would know his hat must be of the other color. Since D doesn't say anything about this, C can divine that his hat and B's must be of different colors - and since he can see B's hat, that gives him the color of his own.

Beyond that, I think you're getting tangled in the concepts of correctness and knowledge, and the idea that greater knowledge always leads to greater correctness. Intuitively this seems plausible, but there's no mathematical reason why it should be so; and another angle on it might show why the intuition is wrong. Think of the problem as pulling balls without replacement from a bin that has a (known) equal number of balls of two colors, and attempting to guess the color of the next ball pulled. After each pull we 'know' an equal amount about the distribution of the balls remaining in the bin - we have perfect information about it! - but there's no correlation between that and our odds of being able to guess the next ball; the latter is simply an artifact of the skew in the data so far. For instance, if we have a bin with six balls (3 Black and 3 White) in it and start by pulling out two Black balls, then we can 'guess' with 3/4 chance that the next ball will be White; but our knowledge isn't in the 75% chance that our guess is correct, it's in the 100% information that the remaining balls are WWWB. Contrast this with starting by pulling out a Black and a White ball; we can't guess at the color of the next ball with any better than 50-50 chances, but we still have the 100% knowledge that the remaining balls are WWBB. The two concepts - what we know about the worldstate and what our odds of guessing a random sample are - are basically orthogonal to each other.

share|improve this answer
3  
I understood the question differently. The answer to the puzzle is irrelevant: The fact that D has more information than C still gives an "educated blind" guess by D lesser chances of being right than an "educated blind" guess by C (assuming OP's calculations etc are correct). Normally one would expect that the higher information you have, the better your chances of making a guess in general... –  Aryabhata Jun 24 '11 at 21:44
    
@Aryabhata: that's exactly what I meant to ask. I've updated the question to clarify. –  shambulator Jun 24 '11 at 21:47
    
@shambulator I realized this after my initial answer - I've edited this answer now to reflect that. Sorry! –  Steven Stadnicki Jun 24 '11 at 21:53
    
not to worry, the conclusion in your amended answer and the analogy leading up to it have given me a lot to chew on :) Thanks for answering! –  shambulator Jun 27 '11 at 19:38
add comment

With the aim of making this question/answers post self-contained, I've inserted the image from the linked puzzle, below, followed by the solution given in that link.

Four Men and a Hat

enter image description here

Shown above are four men buried up to their necks in the ground. They cannot move, so they can only look forward. Between A and B is a brick wall which cannot be seen through.

They all know that between them they are wearing four hats--two black and two white--but they do not know what color they are wearing. Each of them know where the other three men are buried.

In order to avoid being shot, one of them must call out to the executioner the color of their hat. If they get it wrong, everyone will be shot. They are not allowed to talk to each other and have 10 minutes to fathom it out.

After one minute, one of them calls out.

Question: Which one of them calls out? Why is he 100% certain of the color of his hat?

This is not a trick question. There are no outside influences nor other ways of communicating. They cannot move and are buried in a straight line; A & B can only see their respective sides of the wall, C can see B, and D can see B & C.

Spoiler/solution, and see Steven's answer for clarification

C calls out that he is wearing a black hat. Why is he 100% certain of the color of his hat?
After a while, C comes to the realization that he must answer. This is because D can't answer, and neither can A or B. D can see C and B, but can't determine his own hat color. B can't see anyone and also can't determine his own hat color. A is in the same situation as B, where he can't see anyone and can't determine his own hat color. Since A, B, and D are silent, that leaves C. C knows he is wearing a black hat because if D saw that both B and C were wearing white hats, then he would have answered. But since D is silent, C knows that he must be wearing a black hat as he can see that B is wearing a white hat.

The 100% certainty possessed by C is a function of the meta-knowledge possessed by the men. Each man knows that each man is wearing 1 of 4 hats, 2 of which are black and two white. Each man's life is at stake, so we can assume each knows well enough (or figures out) not to shout out carelessly to "guess" the color of his hat.

OP's challenge: Assume the given distribution of hats and positions. Suppose that their lives are not at stake...That each is simply asked to guess the color of his own hat, and asked to call out his choice of color simultaneously in chorus with the others. Then we can determine the probability that any given man has of guessing correctly; as the OP suggests, C has the greatest probability of being correct, though in this challenge scenario, C can not be certain (since he can learn nothing from the silence of the others in this situation.

My conjecture: If $P(X)$ denotes the probability that X guesses correctly, then $$P(A) = P(B) = P(D) = 1/2 < P(C) = 2/3$$

Note: Of course this depends on the distribution of hats as shown in the image above, for if they are distributed such that B and C are each wearing the same colored had, then D would see this, and thus be able to assert, with certainty ($P(D) = 1.0$) the color of his own hat.


share|improve this answer
    
I think it is helpful to include the diagram and original problem here. I think it would be a bit better to put it in the original question, but am not hard over on that. –  Ross Millikan Jun 27 '11 at 4:08
    
@Ross: thanks. Yes, perhaps I should have inserted the image and text accompanying the problem in the post itself, but the last time I did that (after getting no reply from the OP to do so)...the OP "snapped back" at me for doing so? –  amWhy Jun 27 '11 at 14:28
add comment

C knows that B is white. If he where white D would of called out Black. However, he doesn't so C knows D is confused. So C must be Black.

share|improve this answer
add comment

I like to think about it in terms of the amount of information that each person has about the hats.

At first, D has more information since he sees two hats in front of him. If they are the same color, he can know with certainty what colors every man has. Notice that when C and B have different colors, D knows C's and B's hat color, that information just happens to be useless in figuring out D's color.

Because D is silent, that signals to C that D sees two different color hats. At this point, C has obtained all of the information that D has: he knows there are two different colors in front of D, he knows B's color, that means that he can figure out his own color.

Now, C doesn't have a higher chance at guessing a given person's hat color than D: They both have a 0.5 chance to guess A's hat color, they both have a 0.5 chance to guess D's color, they both know B's color, and they both know C's color.

It just turns out nicely for C that he is one of the people whose hat colors D and C both know about.

To introduce a modified challange: if the task were to yell out C's hat color right away, D would know for certain, C would have the increased probability of $2/3$ and A and B would be stuck with the random guess of $1/2$. D still knows more.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.