Thursday, February 23, 2012

The Prisoners and the Hats: A Logic Puzzle

Are you ready to feed your inner geek? Let's go.

Five men are doomed to be executed by firing squad. On the night before their execution they are given a chance to spare their lives. They must follow these instructions, and if any prisoner violates the rules then all the prisoners will be shot:
  1. The prisoners will be brought to the wall, where they are to form a line, each one standing about four feet apart from the other.
  2. The prisoners will then turn to the right, so that they are standing back to front. The wall will be on their right, and the firing squad will be on their left.
  3. No prisoner may turn around to look at the prisoner behind them. If anyone turns around, everyone will be immediately shot.
  4. They are free lean sideways and see the prisoners in front of them if they like, but they must not turn around to see the prisoners behind them.
  5. No prisoner may touch the other prisoners, or all five will be immediately shot.
  6. Starting from the back of the line, the warden will place one hat upon each prisoner's head. The hat will be either white or black, based on the flip of a coin. None of the prisoners will be able to see the color of the hat that is placed on their own head. They can see the hats of the prisoners in front of them, but they must not turn around or look behind them, or all five prisoners will be shot.
  7. After all the hats have been placed, each prisoner must guess the color of their hat. The prisoners will be asked one by one, starting with prisoner 5 at the back of the line, moving forward until prisoner 1 at the front of the line has answered.
  8. When asked, each prisoner must say either "white" or "black". If the prisoner says anything else, all prisoners will be immediately shot. Each prisoner must answer right away. There will be no time to think about the answer or mull it over.
  9. They must answer in English. Prisoners may not vary the speed, pitch, emotion, accent, tone, etc. of their voice so as to convey more information than the mere color of their hat.
  10. If the warden thinks the prisoners are trying to bend the rules or quibble in any way, all the prisoners will be shot.
After all the prisoners have given their answers, those who correctly guessed the color of the hat that they are wearing will be spared and set free. The rest will be shot.

The prisoners have all night to think about their quandary. They stay awake figuring out a way so that they can pass the ordeal together and spare the most lives possible. They are allowed to talk freely among themselves, prepare their plan, and practice it until the morning.
What will they do?

Assumptions:

  1. The prisoners all share the same cell, and are free to say whatever they want, and rehearse whatever plan they come up with.
  2. They are altruistic, and each would give his life for the other if it meant that more lives could be saved than lost.
  3. There are no mirrors at the place of execution. Just a large empty brick room with the firing squad at one end.
  4. None of the prisoners knows anything about the toss of the coin or the hat on their own head.
  5. Only the prisoners behind you know the color of your hat. Neither you nor anyone in front of you can see the color of your hat.
  6. The coin-toss is truly random. There is no pattern to who gets a white hat or who gets a black hat.
Answer:

The person in the back of the line has no information to work with. His odds are at best 50/50. So whatever he says, he might as well use his chance to save the lives the rest.

One solution would be for prisoner 5 to shout the color of prisoner 4’s hat. Prisoner 4 can then be spared. This can be repeated with prisoner 3 and 2. Prisoner 1 can say whatever he wants. This solution will guarantee that at least two prisoners are spared.

There is a much better solution, which is guaranteed to save 4 lives. Pretend you are one of the prisoners. Before everyone begins, all prisoners must count the number of white hats that they see in front of them and remember that number. As each prisoner behind you calls out the color of their hat, you must add one to your total every time you hear the color “white”. When it gets to your turn, if the number in your head is even then you shout out “white”. If the number in your head is odd then you shout out “black”.

Let’s work through an example. Suppose that everyone’s hat is black. All prisoners will have a count of 0.

  1. Prisoner 5 sees 0 white hats. Since 0 is even, he shouts “white”.

  2. Prisoner 4 hears “white”, and his count becomes 1. Since 1 is odd he shouts out “black”.

  3. Prisoner 3’s count is also 1, so he shouts out “black”

  4. Prisoner 2’s count is 1, so he shouts out “black”

  5. Prisoner 1’s count always starts at zero, so he has to pay attention to what the prisoners behind him say. Since he only heard one prisoner shout “white”, his count is 1, and he shouts “black”.

Prisoner 5’s answer was wrong in this case. He dies by firing squad, but his four other mates get to walk out alive.

That seemed way too easy. Let’s do it again. Suppose that everyone’s hat is white.

  1. Prisoner 5 sees 4 white hats. That’s an even number so he shouts “white”.

  2. Prisoner 4 sees 3 white hats. He heard prisoner 5 shout white, so he adds 1, which brings his total to 4. Since 4 is even number, he also says “white”.

  3. Prisoner 3 sees 2 white hats. Both prisoner 4 and 5 said “white”, so he adds two to his number, which brings his total to four. Again, he says “white”.

  4. Prisoner 2’s total starts at 1. He adds 3, which gives him 4, so he says “white”.

  5. Prisoner 1 has been keeping careful count. He is at 4, so he says “white”.

This time prisoner 5 was correct, so they all get to live.

Still don’t believe me? Let’s alternate so that prisoner 1 is white, 2 is black, 3 is white, 4 is black, and 5 is white.

Ready?

  1. Prisoner 5 counts 2 white hats. That’s even so he shouts “white”.

  2. Prisoner 4 sees 2 white hats. Since prisoner 5 said “white”, he adds one and his total is now 3. He shouts “black”.

  3. Prisoner 3 sees 1 white hat. Prisoner 5 said “white”, so his number is 2. That number is odd, so he shouts “white”.

  4. Prisoner 2 sees 1 white hat. His count is now 3, which is even so he shouts “black”.

  5. Prisoner 1 sees 0 white hats, but he’s been listening and his mental total is 2. He shouts “white”.


This system works for any combination of white and black hats, and is guaranteed to spare the lives of the first four prisoners. Prisoner 5 will never have more than a 50/50 chance.

Try some combinations for yourself.

Application:


Computers use a system of error-checking called parity whenever they have to transmit data across a wire, or store it in a memory chip. Depending on the algorithm, the receiving computer can tell if there was an error and ask for a transmission. Some algorithms will allow the receiver to figure out which bit got garbled and correct the problem. Look up “error detection and correction” on Wikipedia for more information.

For more discussion you can check out this article on Wikipedia

No comments:

Post a Comment