# Hats and prisoners

Score Points: 5Solvers: 10

10 prisoners are given a chance of survival by the jailer. The jailer tells them that the next morning, he will have them stand in a queue (so that the last person can see the nine people in front, the second last people can see eight people in front of him, and so on), and then place either a red hat or a purple hat on each person's head. The person hence will be able to see the color of hat for people in front of him (but not his own hat). The jailer will then start from the last person, and ask each person "What is the color of hat on your head". The person can answer "red" or "purple". If the person's answer is correct, he will be released, else he will be killed. The jailer will then ask the same question to the second last person, and so on. The prisoners have the night to figure out the strategy so that maximum number of prisoners can survive (on a guaranteed basis). What is the maximum number of prisoners that one can guarantee will survive?

Show Hint >>You need to

Login/

Register to see the hint.

Try thinking about how the first prisoner can give maximum information to the rest of them about the colors of their hats.
(Use odd and even.)

The prisoners assign each of the colours a number. Let’s say red hats = 1 and purple hats = 0. The last person will look at the hats of everyone in front, add up their hats’ numbers, and then according to another predefined code, will tell them whether that sum is odd or even while proclaiming the colour of his hat. Let’s say red = off and purple = even. Now the second last person knows whether the sum of all the hats he sees + his own is odd or even. Using this information, he can tell whether his own hat is red or purple. The third last person can now subtract 2’s hat number from the original number given by 1 to know whether the sum of everyone in front of him and him is odd or even. This requires everyone to listen to everyone’s answers and keep track of it mentally. Let’s look at an example. Using the code above, the following is the order of hats:

1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |

1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |

Here, 1 can see everyone from 2-10 and 10 can see no one. Prisoner 1 will calculate the sum of hats 1-10 as 5, and say red because it is odd. Now 2 know that the sum of him + everyone in front is odd. He sees that the sum of everyone in front is 5, which is odd, so he must be 0 otherwise prisoner 1 would have seen an even sum. No. 3 now know that odd – 0 is odd, so the sum of everyone in front of him and him must be odd. He again counts 5 and reasons that he must be 0. No. 4 knows that odd – 0 is odd. He will see an even sum, so he will know that he must be a one, because even + 1 is odd and the count was odd before him, so he will say purple. The same logic will be used by each prisoner. This means everyone except prisoner 1 has a 100% chance of guessing the colour of their hat correctly, which guarantees a success rate of at least 9 out of 10 prisoners getting free.
See - https://www.khanacademy.org/math/recreational-math/brain-teasers/v/alien-abduction-brain-teaser

Education - This is a contributing Drupal Theme

Design by

WeebPal.