Monday, February 20, 2017

Riddle of the Week




Riddle of the Week: The Puzzle of 100 Hats

Difficulty level: Hard



Problem

One hundred prisoners are lined up single file. A blue or red hat is placed on each of their heads randomly. The prisoners cannot see the color of the hat on their own head, but they can see the colors of all the hats in front of them. The prisoner in the back can clearly see all 99 hats in front of him. The 50th prisoner in line can see the 49 hats in front of him, and the prisoner in the front of the line cannot see anything but the forest before him. Also, the prisoners don't know the proportion of red hats to blue hats in advance—it could be 50/50, but it could also be any combination that adds to 100.
A guard is going to walk down the line, starting in the back, and ask each prisoner what color hat they have on. They can only answer "blue" or "red." If they answer incorrectly, or say anything else, they will be shot dead on the spot. If they answer correctly, they will be set free. Each prisoner can hear all of the other prisoners' responses, as well as any gunshots that indicate an incorrect response. They can remember all of this information.

Before the executions begin, the prisoners get to huddle up and make a plan. How can the prisoners ensure that the most people possible survive?

Hint

There is a way to ensure that the vast majority of the prisoners survive.

No comments:

Post a Comment