A Prisoner ProblemSeptember 28, 2010
I went to a linguistics talk in college and learned a cool fact from sociology: across cultures and ages, human beings are interested in stories that have to do with
- Death and danger
- Relations between the sexes
These three topics might be called the three universal areas of human interest. “It’s worth noting,” said the researchers, “that these are also classically ‘off-limits’ areas in school.” How funny, I thought.
Perhaps the interest in death, danger, and power is the reason we see various prisoner’s problems cropping up in mathematics. Here’s a fun one I just saw online, and which I thought about years ago… I don’t remember my previous solutions, though. I can definitely come up with a strategy to save at least 10, guaranteed, though I’m sure it’s possible to do much better.
Here’s the problem:
A warden tells 20 prisoners that they can live if they survive the following game: tomorrow the warden will line up the prisoners single file (at random), facing forward and place either a red or blue hat on each prisoner. Each prisoner can only see the color of hats infront of him. The warden starts from the back of the line and asks each prisoner in turn what color hat they think they are wearing.
If a prisoner answers correctly they live, otherwise they die. No communication is allowed between prisoners once the game starts and they can only shout “red” or “blue” when it’s their turn. The prisoners have the evening to discuss a strategy. What is the best strategy for the prisoners? How many prisoners can be guaranteed to live?