| Easy | Strategy |
100 prisoners are lined up and assigned a random hat, either red or blue. There can be any number of red hats. Each prisoner can see the hats in front of him but not behind. Starting with the prisoner in the back of the line and moving forward, they must each, in turn, say only one word which must be "red" or "blue". If the word matches their hat color they are released, if not, they are killed on the spot. They can hear each others answers, no matter how far they are on the line. A friendly guard warns them of this test one hour beforehand and tells them that they can formulate a plan where by following the stated rules, 99 of the 100 prisoners will definitely survive, and 1 has a 50/50 chance of survival. What is the plan to achieve the goal?
Hint
Red and blue can be thought of as 0 and 1. Think of modulo 2 sums now.
Solution
Number prisoners from 100 to 1, with 100 being the last person in line, being able to see 99 other hats. Prisoners agree that if the number of red hats that the 100th person can see is even, then he will say “red”. if they add up to an odd number, he will say “blue”. this way number 99 can look ahead and count the red hats. if they add up to an even number and number 100 said “red”, then 99 must be wearing a blue hat. if they add up to an even number and number 100 said “blue”, signalling an odd number of red hats, number 99 must also be wearing a red hat. number 98 knows that 99 said the correct hat, and so uses that information along with the 97 hats in front to figure out what color hat is on 98’s head.
Latest solved Puzzles
Color Switches Weird Sequences Intersecting Pillars Consecutive sums Scaling a Square Difficulty Level
| © BRAINSTELLAR |