# Save 10 prisoners

godchuanz
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?

Jimmy Snyder
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).

0m3ga
get the executioner...10 against 1 aint bad odds

godchuanz
jimmysnyder said:
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).

Interesting answer, but let's say they can only say "white" or "black", no other words are allowed. How then?

Jimmy Snyder
godchuanz said:
Interesting answer, but let's say they can only say "white" or "black", no other words are allowed. How then?
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-
...

Homework Helper

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?

Jimmy Snyder
NateTG said:
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?
Answer in white: First two prisoners decline to guess, the third takes a wild guess.

Homework Helper
Not bad Jimmy, but it's possible to do better.

Jimmy Snyder

NewScientist
OP - do they know how many black and white hats there are?

NewScientist
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

Homework Helper
jimmysnyder said:
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?

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.

Jimmy Snyder
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.

nnnnnnnn
NateTG said:
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?

...

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%?

Homework Helper
nnnnnnnn said:
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%?

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.

Jimmy Snyder
nnnnnnnn said:
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%?
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.