Friday puzzle: Four Men in Hats

A fine puzzle from Mycoted.

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.

Visit Mycoted for the answer

• [acerplatanoides]

  C cannot know that D can see B and C, so C cannot assess what D is capable of seeing.

  • [Reverend Loki]

     ” Each of them know where the other three men are buried.”

    It is natural to assume that each knows which direction each one is facing as well. 

    • [acerplatanoides]

      if that were true, then it would be natural to assume that each know which hat each one is wearing as well.

      It basically a test of whether C noticed what hat D had on when C saw D get buried. Since they can’t communicate, I’m not sure how else C could know anything about D’s head.

      • [dave moore]

        D can see B and C. C can see B.  Everyone knows who can see who.

        • [acerplatanoides]

           If they all know who can see whom, then why don’t they know about the hats? Just ‘because’?

        • [Andrew Parliment]

          The rather disturbed executioner put the hats on after burying them, in order to give them a brain teaser which they are in all likelihood too afraid to work out.

      • [Peter]

        No, it would not be natural to assume that, because that is explicitly ruled out. 

        Aside from which, knowing where they are located, without the information that D can see C and B, there is no solution to the problem that allows any of them 100% certainty.  At which point, the only solution is a coin toss anyway, so he’s no worse off by guessing what he guessed anyway.

        Also, in your last point you’re assuming that they were buried with the hats on. It’s quite possible that they were buried, blindfolded, and then the hats were put on them as part of the setup. All we know for sure is that they DON’T know what hats were put on them, other than that two were black and two white, and whatever they could see when the game began.

        • [Jason Oliver Smith]

          Negative.  Because D can see both B and C, if they were the same color hats he would shout out his own hat color to save them.
          Spoiler, answer below…
          However, he cannot know for sure.  That tells C that D sees one of each hat.  Since C can see that B is a white hat, he knows that he must have a black hat.

        • [Donald Petersen]

          NVM

        • [Peter]

           I’m not sure why you’re disagreeing with me, considering we seem to agree on the conditions and the solution. :)

        • [acerplatanoides]

           But A B and C cannot know that about the orientation of D. Can they?

        • [acerplatanoides]

           explicitly ruled out? By what method were 4 people buried  in such a way that they knew exactly where each other were, and which direction their heads were facing, but couldn’t make out the hat? Come on. Yeah, it’s a logic puzzle, sure, but it’s not a plausible puzzle.

          Put in some one way mirrors, and we can have a conundrum.

        • [ocker3]

          They were told that information? They were buried, and then the hats were put on from behind them so they couldn’t see?

          It’s an unlikely puzzle, somewhat implausible, but not impossible.

          Edit: Although the cultures who tend to bury people don’t tend to have much interest in toying with the people facing execution, they just get on with it.

        • [acerplatanoides]

           agreed ocker3. If someone buried me up to my head and asked what sort of hat i was wearing I’d say I was wearing the hat from their fathers nightstand.

• [raines]

  Alternate caption: someone finally got fed up with Devo.

• [UFIA]

  No answer.  They got bOINGED.  

  • [Marja Erwin]

    Well, there is an answer, C speaks up because D doesn’t. But there’s no working link to the source of the puzzle.

• [jandrese]

  In the description of the problem it says that everybody knows where everybody else is, so C knows that D can see B and C. 

  I can’t get the answer to load, but my guess is

  [spoiler]C calls out, inferring from D’s silence that both B and C have different color hats, and because he can see B’s hat, he knows his is the opposite color.

  If both B and C were wearing the same color hat, D would be able to answer that he had the opposite color hat.[/spoiler]

  If you want a bit more challenge, try http://xkcd.com/blue_eyes.html

  • [OgilvyTheAstronomer]

    Yup, I came to the same conclusion; the clincher is the “after a minute” remark — obviously that the answer is non-immediate is itself a crucial bit of information.

  • [tedrock]

    If anyone wants to check out an explanation of the answer on an alternate site, check it out here:
    http://camworld.org/misc/teasers/fourmen.html

    • [TheOven]

       Which gets blocked for being unsafe (to my office apparently).

      • [John Carter]

        Here’s the problem on Wikipedia: http://en.wikipedia.org/wiki/Prisoners_and_hats_puzzle#The_solution

  • [SamSam]

    Yup, came to the same conclusion.

    This puzzles are very frequently dependent on the answer not being immediately forthcoming, and the resulting silence being taken as a clue.

    I remember one about 100 monks (and colors hats again, I think), that used a gong to “synchronize” everyone’s thinking. After the 99th gong-strikes all the monks simultaneously knew the color of their own hat.

  • [Marja Erwin]

    I assume that 99 blue-eyed [and between 0 and 100 brown-eyed] people have already left, having discovered their eye-colors in various unstated ways, when the guru speaks up, and the last blue-eyed person leaves.

  • [SamSam]

    I looked at the XKCD puzzle and have to take issue with Randall saying it’s the “hardest logic puzzle in the world.” Maybe I’m just used to similar puzzles (like my vague memory of the 100 monks puzzle in the previous comment), but it seemed trivial to work up from the “one blue-eyed guy and one brown-eyed guy” version up to the 100/100 version.

    Now, unless the guru changes what she says, those poor brown-eyed guys have to stay on the island for ever…

    • [Jonathan Roberts]

      I would have to question why the guru is in charge of the people in the xkcd problem, seeing that there are literally hundreds of things she could have said that would have allowed them to leave the island that night. “I can see equal numbers of blue and brown eyed people” or “ask the captain” for example. Have none of these people ever looked in a mirror before? If not, have they lived all their lives on the island without any technology, in which case it’s a bit odd that they all want to leave now.
      If I saw the 100 blue eyed people leaving that night, I’d just leave the next day and take the very slight chance that I had anything but brown eyes. With any luck the Guru would do the same.

  • [Jorpho]

    I also immediately thought of the XKCD blue-eyes puzzle, from which this puzzle directly follows.

  • [ChipN]

     This is an allegory to 2012 US elections. We are all buried up to our necks in 100% of GDP Federal deficits, with a private international bank cartel Fed wall of debt in front of us, never been audited, charter about to be renewed for another century, and wall of woe is growing taller brick by QEn brick. We can’t see our own hats, because the media only reports the ‘Given Wisdom’ — the ‘flash and sizzle’. And if we guess wrong on November 7th, we’ll all starve as paupers. Therefore, no matter what color hat you’re wearing, red or blue, you hope the wall falls on A, the Mil.Gov establishment portion of US population.

    • [tomrigid]

      You are buried up to your neck — with your feet in the air.

    • [Petzl]

      Yes, problems such as these always go critical when Democrats are in office. And the solution is to cut taxes, allow school prayer, and have more concealed carry laws.

  • [Juan Figueredo]

    That answer adds several new assumptions:
    1. Each one of them assumes that the others are rational.
    2. Each one of them assumes that the others will figure out the answer in less than one minute if there’s one available, and will call out.

    Those are tricky assumptions if your life is on the line.

• [GawainLavers]

  “This is not a trick question. There are no outside influences nor other ways of communicating.”

  The last is not, strictly speaking, true.

• [Matt Bailey]

  Here’s the answer from the Google cache.

• [cellocgw]

  This is a famous “interview question” puzzler.  The so-called correct answer depends on the assumption that all four are reasonably intelligent and their thought processes proceed at the same pace.  There are much better “guess the hat color” puzzles which do not depend on such assumptions but purely on a deterministic algorithm.

  • [desiredusername]

    Indeed. It can not quite be 100%. This is a model of duration dependence

• [Senor Schaffer]

  I read the answer I still have no clue.

  me<——dead

• [wysinwyg]

  If B and C had the same color hats, D would know the color of his hat.  Since D does not say anything,  C knows that his hat does not match B’s.  But C can see B’s hat, so C knows that his hat must be black.

  Did I get it?

  • [Peer Resources]

    I think you got it. What’s funny about this puzzle is that it seems to be an example of the solution is more complicated than the puzzle.

    • [An Infinitude of Tortoises]

      Which, in puzzles and in general, is so often the case!

• [Jack Nymus]

  SOLUTION:

  There are six possible scenarios:

  # – A – B – C – D
  ——————–
  1 – B – B – W – W
  2 – B – W – B – W
  3 – B – W – W – B
  4 – W – W – B – B
  5 – W – B – W – B
  6 – W – B – B – W

  In scenarios #3 and #6, D can see that there are two of the same hats. That will mean that D will answer instantly, since he knows with 100% certainty what color his hat is based on the matching two hats he can see.  Since it has been a minute and D is still quiet, C gets to thinking.  He runs through all these possibilities in his head, eliminating #3 and #6.

  1 – B – B – W – W
  2 – B – W – B – W
  4 – W – W – B – B
  5 – W – B – W – B

  Since he sees a white hat in front of him, he knows for sure that it has to be #2 or #4.  In both cases, his hat is black.  D’s silence means that C can be absolutely sure of his hat color.  This works no matter what the arrangement of the hats are.  Either D or know, or C will know.  It is NOT particular to this exact example of the problem.

  • [An Infinitude of Tortoises]

    Hmm, I strongly suspect you’ll enjoy my variation on this puzzle, posted further down!

• [Dan Hibiki]

  D shakes his hat off and sees that it’s white9or looks up to check it). By process of elimination works out that A is black. Everyone lives but are forced to remain in the draconian hard labor camp till they collapse dead from exhaustion.

• [Boundegar]

  I got it.

  If B = C then D knows what color he’s wearing.  If he saw two whites, he has to have black.

  After a minute, D hasn’t shouted.  Therefore B =/=C.

  C looks forward, sees white.  C knows he must be wearing black.  But he lacks confidence, and says nothing, and they all die.

• [MoZeu]

  Fun!  It took me longer than a minute, but I got it.  C waited for D to call out and, when D didn’t call out, C knew that he and B had to be wearing different colored hats.  He sees that B is wearing white, and so he calls out “Black” and is correct.

• [Gyrofrog]

  As Rev. Jackson said, “the question is moot:” any captor who is that sadistic and psychopathic is going to shoot everyone regardless of right or wrong answers.

• [Henry Pootel]

  A, being behind the firewall, relies on his black hat skills to get inside and determine the other three.  Whether he used conventional means or social engineering is not clear at this time.

• [awjt]

  C calls out, “I have a white hat.”  D responds, “Shut up you idiot, you’ll get us all killed!”  C corrects himself, “No, sorry, my hat is black.”

• [Gregg Grose]

  I would fire the executioner – so much digging, burying and masonry.

• [gmarsden]

  I’m not feeling smart enough to work this out right now, but I’m wondering if there is a scenario where C waits *too* long and somebody else concludes something incorrect from C’s lack of response. Is there such a scenario?

  • [gmarsden]

     Actually, I guess not, in this case. Either D figures it out or C does. No need for further thinking. I wonder if there a slightly more complex problem where timing could matter… like putting an E behind D, maybe.

  • [An Infinitude of Tortoises]

    Good question, and one I’ll have to ponder.  Of course in the current scenario, if C waits too long to pipe up the executioner will conclude it’s time to shoot, which might well be considered incorrect.

• [mrtut]

  Excuse me, buried people and executions? Can’t it be a puzzle about muffins and unicorns? 

  I would blame those silly/evil mid-20th century quiz-inventing nerds/sociopaths. Yet still, the way the question is posed exhibits traits of the culture it is posed in. 

  Say, you have two prisoners and three civilians. If you taze them all, how many people have you made cooperative?

  • [An Infinitude of Tortoises]

    There’s a pretty similar puzzle (see my comment later on) involving three wise men — though there, of course, one may object that they might just as well be three wise women instead.

    Anyhow, these flawed concrete details at least spare us from facing the equivalent puzzle posed in symbolic logic terms.

• [Nathan Hornby]

  I think my brain broke a little bit.

• [knappa]

  Without reading any other comments: If B and C had the same color hat, then D would see that either the 2 black or 2 white hats had been used up already and D would know that he had the opposite color. Since D did not call out immediately, B and C know that they have different color hats. Then C, who can see B, knows that he has the opposite color of B. Thus C knows his hat’s color.

• [Scott Rubin]

  Believe me or not, but I actually solved this puzzle very quickly and all by myself. I’m feeling pretty good about myself!

  • [An Infinitude of Tortoises]

    Nothing satisfies like the efficacy of applied reason!

    Well, maybe chocolate….

• [chgoliz]

  C knows that B has white, and D hasn’t spoken up, so it must be that C has black (if both B & C had white, D would have known to say black for him/herself).

  Edit: I see jandrese explained it better above. Aw, heck, and a few others as well!

• [Jose]

  I deduced that it was C, but what tripped up mostly about this puzzle is the statement “In order to avoid being shot, one of them must call out to the executioner the color of their hat.”  Shouldn’t that be “his hat”?  Initially, I thought this meant that someone had to call out which color hat each of the men were wearing, which I think is impossible for any of the men to deduce. This is a case of “their” being used as a singular possessive, which I find odd.

  • [Dewi Morgan]

    Singular “they” has long been a part of English, but in more recent times (1800s and on), the rather wrong-sounding generic “he” has become common, instead; and in America, even more jarringly, generic “she” has become popular since the 1980s or so.

    Obviously, either “he” or “she” is sexist, and heavily biased both against those not mentioned, and against those who don’t fit traditional gender pigeonholing.

    While many grammar books you will find in schools continue to recommend use of generic “he”, readers increasingly find it jarringly sexist and inappropriate: it should be avoided where possible. Users of generic “she” lack even this defense of tradition: they’ve just made a conscious choice to use a sexist term.

    However, both of these sexist sillinesses are infinitely better than formations like “he/she”, “(s)he”, and so on; or the derogatory “it”; or made-up words like “ey”. Although Spivak nouns have a certain geeky MMO cred, just about nobody will understand you if you use them, and even those that do will still find it more jarring than just using the correct word: “they”.

    • [KvH]

      Except they are specifically called out as being men in the first sentence. Once gender is known he/she can be appropriately used. It’s only sexist if you assume they are a particular sex.

      • [Dewi Morgan]

         Ooh, good call! :D I agree, yes: “he” would have worked just fine in this situation!

        That said, “they” still feels fine to me too: but I do admit it’s not *as* good in this situation as “he”, which has the definite edge in terms of clarity.

• [timquinn]

  Wasn’t this an episode of Lost?

• [Erik Lehtonen]

  I feel like calling BS on the answer because *cough* spoiler *cough*…if the lack of an answer from one party (that explicitly says in the solution, they cannot know what color their hat is) is used as evidence to a conclusion, I don’t think C can answer with 100% certainty (which was a requirement for the correct answer) Let me draw a ridiculous and hyperbolic analogue: “They did not convince us within a reasonable time that they were not stockpiling yellowcake uranium, which thus proves they must have it!”

  • [ahrimano]

    Well put, guess I should have read this before posting hehe.

• [ahrimano]

  PEDANTIC SPOILER ALERT – I’ve used lateral logic questions like these in interviewing candidates for various jobs and they are inherently flawed. The key here is the mention that per capita each head remains silent long enough for C to realize that D doesn’t know. The issue is that C knows for “100%”; which is just plain impossible given the information provided, and no matter what “percent” is quoted nothing is 100% for sure (perhaps more pertinent in a discussion on physix) . The factors are infinite in setting up a problem where C knows 100% for sure; perhaps D had perished without his knowledge from dehydration, they may be buried in a cellar with all lights out, perhaps D is a mute, and possibly C is deaf . . . the factors are infinite and the problem is flawed thus. Maybe people who think they are “smart” shouldn’t be writing logic puzzles trying to root out the uber-intellects and then think themselves a genius when a true genius (not me) doesn’t understand the question because it is so freaking transparently flawed. For this question of logic to truly be answerable every conceivable relative factor must be listed within the question. If you have 10 blue and 10 black socks in a drawer and the light in the room is off how many socks must you pull out before you know you have 2 of the same color socks?

  • [An Infinitude of Tortoises]

    You’re absolutely right — that is pedantic.  :-)  My response is that a smart person, rather than seeking to evade the problem via endless technical quibbles, would address it head-on in the terms obviously intended — as an exercise in abstract logic.  It is couched in concrete terms, with their inevitable imperfections and loopholes, rather than posed in symbolic-logic notation merely as a convenience to the puzzler.

    Heck, you’d probably cheat in the Kobayashi Maru test!

    (Nonetheless, your objections do merit mentioning.  The real world has its place, after all.)

• [acerplatanoides]

  51 comments….no Safety Dance? Everybody look at your hands!

• [An Infinitude of Tortoises]

  This prisoners and hats puzzle reminded me of “The Puzzle of the 3 Hats” that I first read about in 2009 and could actually be considered a somewhat simpler variant, despite featuring four hatted parties rather than three.  In the “3 Hats” puzzle, it’s three wise men (wise women would serve just as well) lined up in a row, just like B, C, & D in illustration above (there’s no “A” here), but wearing hats picked randomly from a selection of two black and three white.  We, the puzzlers, don’t know who got what hat color.  The wise folk are invited to figure out their situation (no peeking, of course), and after a while the first wise person (i.e., “B”) says his hat is white; the puzzle for the reader is to figure out how that conclusion was reached.  Not very difficult, really, at least to aficionados of applied deductive reasoning.  Anyhow, it always struck me how, in this scenario, smartypants “B” was able to announce “White!” so confidently — but suppose “B” had been wearing a black hat instead.  What then? 

  That is my new puzzle for you, gentle readers! 

  Same set-up as in the “3 Hats” puzzle, but instead of being told what the wise people say and invited to reverse-engineer the reasoning behind it, one is told only that “B” wears a black hat and asked to figure out who, if anyone, says what, if anything.  Do any of them figure out their hat color?  The clock is ticking; what happens?  I eagerly await your analysis!  Believe me, this variant is even more fun….

  • [rrh]

    If B is b, then only three possibilities, facing left
    bbw
    bwb
    bww

    If it’s bbw, then D will realize he must be white and say so.
    If it’s bwb or bww, then D won’t be certain his hat colour, and we have a similar situation to the Four Men example above, that if C is certain that D can’t answer, he knows his own hat is w.

    But isn’t this a subset of the other version of the Three Hats problem? In order for B to conclude his hat is white, he must know that were it black, either C or D could deduce their own hat colour.

    • [An Infinitude of Tortoises]

      I don’t know whether I’d call it a “subset” but it is similar in the way you mention, yes.

      In any case, your analysis of my variant is fine as far as it goes, but perhaps it could go a bit farther.  Let’s consider the three combinations one at a time.

      When bbw, D will indeed conclude and say this his hat is white.  Then, however, both B and C can confidently say their hats are black.  (With what other color combination could D have reached that conclusion?  None.)

      When bwb, C identifies his hat as white, as you note.  Then, however, B can once again deduce his hat is black, because … but let me deal with the third combination now.

      When bww, exactly the same things happen as with bwb!  C makes the same identification because the hats visible to D are the same, yielding the same silence from D; and B then realizes that only the rightmost pair of wb or ww can result in C’s conclusion, hence leaving black as his own, only possible hat color.

      So the interesting thing to note here is that in all three cases, both B and C will be able to identify their hat color!  Kinda nifty.

      One of these eons, I’ll have to do the analysis for all combinations of hat colors initially stipulated as being worn by a single participant….

• [John Gold]

  Reminds me of the children’s Book a friend of my fathers wrote;”Anno’s Hat Tricks”  (It was originally wrote with the characters John and Margaret after me and my sister before the editor got to it). I test read it as a kid and really liked it. http://www.amazon.com/Annos-Hat-Tricks-Akihiro-Nozaki/dp/0153003499

• [Geno Martinez]

  A similar form of this puzzle was featured in the manga Sket Dance, except with people on stairs. Person C is 100% sure of his hat color, because since Person D can see both hats in front of him and yet hasn’t spoke up, it would mean that Person B and Person C’s hat colors aren’t the same.

  Since Person C can see Person B’s hat, which is white, and since he knows that Person D isn’t 100% sure of his hat color because he hasn’t spoken up, Person C should now know that his hat is black.