Friday, February 24, 2017

Solution to Riddle of the Week

Solution to Riddle of the Week: The Puzzle of 100 Hats

Difficulty level: Hard




With the right plan, you can guarantee that 99 of the prisoners will live, and the remaining prisoner will have a 50% chance. The key is to find a piece of information that the first prisoner can convey using only the words "blue" or "red," a piece of information with only two possibilities.

Solution

The prisoners come up with the following plan: If the first prisoner to speak—the one in the back of the line—sees an even number of blue hats, he will yell out "blue." If he sees and odd number of blue hats, he will yell out "red."

Let's assume the first prisoner to speak yells out "blue," indicating that he sees an even number of blue hats. Then the next prisoner to speak can look at the line in front of him, and if he sees an odd number of blue hats, he knows his hat must be blue to make the number even. Similarly, if he sees an even number of blue hats, he knows his hat must be red to keep it that way. The same logic works if the first prisoner yells out "red," indicating that there are an odd number of blue hats.

The next prisoner in line listens to the prisoner behind him, and takes that information into consideration. If he sees an even number of blue hats and the prisoner behind him yells "blue," making the total number of blue hats odd, then he knows his hat must be blue to make the total number even again (of the 99 seen by the first prisoner). In the same situation, if his hat were red, the total number of blue hats would be odd (of the 99 seen by the first prisoner).

As you go down the line, each prisoner must count how many blue hats are behind them. Then he must consider the blue hats in front of him. If the number of blue hats behind a prisoner plus the blue hats he can see in front of him equals an odd number, then he knows his hat must be blue to make the total number even, or red to make the total number odd (not counting the very first prisoner).
The very first prisoner is the maybe-martyr of the group. He is imparting information to the rest of the group that has nothing to do with the hat on his own head, which he cannot know, and so his chances of living are only 50%.

Editor's Note: If the number of blue hats the first prisoner sees is odd, that means the number of red hats is even. So it is also accurate to say the first prisoner yells out "blue" if he sees an even number of blue hats and "red" if he sees an even number of red hats.

No comments:

Post a Comment