Tuesday, December 8, 2009

The Prisoners' Hats, Part 1


From time to time the Prison for Creative and Unusual Punishment gets overcrowded, so puzzles are administered to selected inmates.  If they pass, they go free; if they fail, the are executed.  On one such occasion, three cells were needed, so three of the cleverest inmates - Albert, Barry, and Carl - were put in a room and given a challenge. A guard showed them 5 party hats - 3 white, 2 black.  The guard then removed the hats from view, walked behind each prisoner and placed a party hat on his head.  Each inmate could see the two other inmates' hats, but not his own; nor could he see the two extra hats that were not placed on heads.

The guard said, "If anyone can tell me with absolute certainty the color of his own hat, you may all go free.  However, under no circumstances may you communicate the color of anyone else's hat."

He first asked Albert.  Albert is a very honest and intelligent (ie perfectly rational) person, but he was dumbfounded.  "I don't know", he said, "there's no way of knowing."

He then asked Barry.  Barry was equally intelligent and rational, but he also could not say.

The guard said, "I regret that I have to execute you three, but seeing as Carl is blind, he's not going to know.  You have failed."

But Carl piped up and said, "But I do know the color of my hat."

What is the color of Carl's hat, and how did he know?






Solution courtesy of Andy Wright:


Albert is first to guess, he knows there are only two black hats.  If
he sees the two black hats on Barry and Carl, then he knows his must
be white.  However, he could not conclude what color his was,
therefore either Barry or Carl must be wearing a white hat.

Barry understands this.  If he sees Carl wearing a black hat, then he
knows he must be wearing a white hat (regardless of what color Albert
is wearing).  However, he also could not conclude what he was wearing,
so Carl must be wearing a white hat.

It's impossible to determine what color either of the other two are
wearing (they could both be wearing white, both be wearing black, or
one of each color).

4 comments:

  1. Since the solution hasn't been posted, I figured I'd go ahead and put in a brief explanation. Fun puzzle, by the way.

    Carl's hat is white, and he can infer this from Albert and Barry's inability to tell the colors of their own hats.

    Given that there are only two black hats available, there are seven possible arrangements of hats among the three prisoners:

    (the table won't go in, because preformatted text is not allowed. Unfortunate. If you like, you can make a table with seven rows and three columns. Let a white hat encode binary zero, and a black hat encode binary one. Then, if Albert's hat color is the MSB, Barry's is in the middle, and Carl's is the LSB, row n is given by the binary representation of n-1.)

    An eighth scenario, in which each of the prisoners wears a black hat, is impossible, since there are only two black hats.

    Consider what Albert can infer from seeing Barry's and Carl's hats. The only way he could make a conclusive determination of his own hat color is if Barry and Carl were both wearing black hats. In that case, Albert would know he was wearing white. Since Albert is honest and intelligent, and does not know that he is wearing white, we know that Barry and Carl are not both wearing black hats -- this eliminates line 4 from the table above.

    Likewise, if Albert and Carl were both wearing black hats, Barry would immediately know that his hat was white. Since he doesn't know this, we can eliminate line 6.

    Finally, Barry knows that he and Carl are not both wearing black hats. If they were, Albert would know that his own hat was white. So, if Carl were wearing a black hat, and Albert's hat were white, Barry would know that his own hat must be white. Since he cannot infer this, Carl knows that his hat is white.

    ReplyDelete
  2. The silence of the other prisoners says a lot - but there are some assumptions here that are being forgotten. I think this page does a good job of clarifying assumptions:


    http://www.programmerinterview.com/index.php/puzzles/hat-puzzle-black-and-white-hats/

    ReplyDelete
  3. What if Carl wears a black hat, and the other two white hats? They both see that there are one of each color and nobody can be sure which is on their head. Maybe if Carl wasn't blind this riddle would work

    ReplyDelete
    Replies
    1. This riddle ONLY works if Carl is blind. If they all can see and are of equal intelligence 1) someone will dash out if they see 2 blacks, so no one has 2 blacks if any hesitation; 2) someone will dash out if they see 1 black and 1 white, since they know their hat must be white; 3) but with more hesitation they all rush out knowing they all have white.

      Albert, Barry, and Carl with 1 = white and 0 = black:

      A B C
      1 1 1
      0 1 1
      1 0 1
      1 1 0
      0 0 1
      1 0 0
      0 1 0

      If Carl is blind, then Albert and Barry could make no inferences based on Carl's actions. C knows he and B aren't both in black since A didn't run out, and he and A aren't both in black since B didn't run out. So the only possibilities now are:

      A B C
      1 1 1
      0 1 1
      1 0 1
      1 1 0
      0 0 1

      Blind Carl knows Albert and Barry would be racing out if Carl had black, because they've made all the same intelligent inferences. So, Carl knows he has white before the others know, if everyone is standing around hesitating.

      Delete