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