Prisoners and Hats Puzzles

Here are some fun logic (math?) puzzles involving hats:

1. Fifteen prisoners sit in a line, and hats are placed on their heads. Each hat can be one of two colors: white or black. They can see the colors of the people in front of them but not behind them, and they can’t see their own hat colors. Starting from the back of the line (with the person who can see every hat except his own), each prisoner must try to guess the color of his own hat. If he guesses correctly, he escapes. Otherwise, he is fed to cannibals (because that’s the canonical punishment for failing at hat problems). Each prisoner can hear the guess of each person behind him. By listening for painful screaming and the cheering of cannibals, he can also deduce if each of those guesses was accurate. Of course, this takes place in some magical mathematical universe where people don’t cheat. Assuming that they do not want to be eaten, find the optimal guessing strategy for the prisoners. (Hint: The cannibals should eat no more than one prisoner.)

2. In the year 3141, Earth’s population has exploded. A countably infinite number of prisoners sit in a line (there exists a back of the line, but the other end extends forever). As in the previous problem, white and black hats are placed on their heads. Due to modern technology, each person can see the hat colors of all infinitely many people in front of them. However, they cannot hear what the people behind them say, and they do not know if those people survive. Assuming that they do not want to be eaten, find the optimal guessing strategy for the prisoners. Assume that there are enough cannibals to eat everyone who fails. (Hint: The cannibals should eat no more than finitely many prisoners. Assume the Axiom of Choice.)

3. There are seven prisoners, and colored hats will be placed on their heads. The hats have seven possible colors (red, orange, yellow, green, blue, indigo, violet), and may be placed in any arrangement: all the same color, all different colors, or some other arrangement. Each person can see everyone else’s hat color but cannot see his own hat color. They may not communicate after getting their hats, and as in the previous problems, they remain in a magical universe where no one cheats. They must guess their hat colors all at the same time. If at least one person guesses correctly, they are all released. If no one guesses correctly, however, the entire group is fed to cannibals. Assuming that they don’t want to be eaten, find the optimal guessing strategy for the prisoners. (Hint: By this point, the cannibals have probably eaten far too much. It would be cruel to force them to eat any more, so spare the cannibals and find a way to guarantee that the seven prisoners survive.)

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: