Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Save 10 prisoners

  1. Aug 17, 2005 #1
    10 prisoners are about to be executed. The executioner gives them each a chance to survive, "I will place a little hat on each of your heads, either black or white. All those who can correctly guess the color of the hat they are wearing will be let off, and all those who can't will be killed instantly."

    Before they enter the execution room, they are given a chance to say their final prayers together.

    After the prayers, they are lined up all facing in a direction, such that the last man can see all the 9 men ahead of him, and the 1st man can only see a wall. Then, the hats are placed on the prisoners, and the executioner first attends to the last guy in the line.

    During the prayers, 1 of the prisoners came up with a brilliant strategy to ensure maximum survival. The big question:
    What is the best strategy such that a maximum number of prisoners will SURELY survive?
     
  2. jcsd
  3. Aug 18, 2005 #2
    Answer in white:
    During the prayers the prisoners agree on the following code:

    Mine is white means that my hat is white and the hat in front of me is white.
    My hat is white means that my hat is white and the hat in front of me is black.
    My hat is black means that my hat is black and the hat in front of me is white.
    Mine is black means that my hat is black and the hat in front of me is black.

    At most one prisoner will die (if they don't screw it up).
     
  4. Aug 18, 2005 #3
    get the executioner...10 against 1 aint bad odds
     
  5. Aug 18, 2005 #4
    Interesting answer, but let's say they can only say "white" or "black", no other words are allowed. How then?
     
  6. Aug 18, 2005 #5
    Loud means one thing, soft means the other.
    -or-
    Hesitation means one thing, prompt reply means the other.
    -or-
    High pitch means one thing, low pitch means the other.
    -or-
    ...
     
  7. Aug 18, 2005 #6

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    Answer in white:

    The back prisoner says black if he sees an odd number of black hats.
    That means that the following prisoner can tell whether he sees a different number of black hats or not (because they're even or odd).
    All the other prisoners can account for the number of other prisoners that have said black, add that to the total of black hats to see, and use the same approach.

    On average, one prisoner will die 1/2 of the time assuming even white/black distribution. Worst case one prisoner dies.


    There's a related problem:
    Let's say you have three prisoners, once again with white and black hats. They pray in forced silence. Then they're asked indiviually if they want to guess the color of their own hat, or they can decline to guess. If any prisoner guesses wrong, or no prisoner guesses, they all die. What's their best strategy?
     
  8. Aug 18, 2005 #7
    Answer in white: First two prisoners decline to guess, the third takes a wild guess.
     
  9. Aug 18, 2005 #8

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    Not bad Jimmy, but it's possible to do better.
     
  10. Aug 23, 2005 #9
    Nate, how about a clue, or an answer?
     
  11. Aug 23, 2005 #10
    OP - do they know how many black and white hats there are?
     
  12. Aug 23, 2005 #11
    Oh!! It doesn't matter, answer to Original post in white


    The back man looks at all of the hats infront of him and counts how many are black and how many are white. He then shouts out the word (black or white) of the hats which have an odd number in front of him.

    There are two situations in this - either the back man survives or not - and here is the results in either case.

    If, the back man lives (for this case by saying black - it does not matter which colour he wears and lives), the man in front knows that the man behind him was wearing a black hat. He also knows, that if he is not wearing a black hat, that there should still be an odd number of black hats in front of him, as the back man declared that there was an odd number of black hats in front of him. The second man now counts how many black hats are left - if there is an odd number, he must be wearing a white hat - if there is an even number he must be wearing a black one.

    Follow this logic through to the end and the lives of all but the first man questioned are guaranteed. The first man has a 50% chance of survival.

    If the back man dies (for this case by saying white - it does not matter which colour he wears and dies). The man in front reasons that if there is still an odd number of white hats infront of him - he must be wearing black, if there is an even number, he must be wearing a whtie hat. and so on as above.


    -NewScientist
     
  13. Aug 23, 2005 #12

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    Obviously, individually, the prisoners will be guessing right and wrong an equal amount of the time, but does the same have to be true for the group as a whole?

    An answer follows in white

    If one of the three sees two hats of the same color, then he guesses the other color. Otherwise he shuts up. This way, the prisoners survive three quarters of the time.
     
  14. Aug 23, 2005 #13
    Brilliant. What threw me was the fact that in the 10 hats case, the executioner decided who would answer first, while in your version, the prisoners themselves decide who will answer.
     
  15. Aug 23, 2005 #14
    There are 4 possible situations:

    1) 3 B, 0 W
    2) 3 W, 0 B
    3) 2 B, 1 W
    4) 2 W, 1 B

    Assuming that each is equally likely, then your solution gives a 50% survival rate, same as last prisoner randomly guessing. Did I miss something that would make it 75% instead of 50%?
     
  16. Aug 23, 2005 #15

    NateTG

    User Avatar
    Science Advisor
    Homework Helper

    Assuming each prisoner gets a white or black hat with an individual probability of 50%, the latter two occur more frequently. (How likely are you to get all heads or all tails if you flip a coin 3 times.) If the goaler is malicious, the prisoners are, of course, SOL.
     
  17. Aug 23, 2005 #16
    Yes. Your assumption that each is equally likely is not true. The probability of 1) is 1/8 and so is the probability of 2) but the probablility of 3) is 3/8 and so is the probability of 4). In short, they all die in cases 1) and 2) for a total of 1/4 of the time, but they all live in cases 3) and 4) for a total of 3/4 of the time.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Save 10 prisoners
  1. Prison systems (Replies: 3)

  2. How good are prisons? (Replies: 5)

  3. Harvard or Prison? (Replies: 36)

Loading...