Setup: There are n prisoners standing in a circle so that everyone can see each other's hats but not their own. An executioner will use a fair coin toss to put a black or white hat on every prisoner. He will then proceed clockwise around the circle and ask each prisoner if they want to guess their hat color. Prisoners may guess or choose to pass, but at least one prisoner must guess. If ANY prisoner guesses their hat color wrong, everyone will be killed.
Question: What strategy can the prisoners use to maximize their chances of living?
The "Default" Solution
The default solution is to have everyone pass until the last prisoner who must guess. They have a 50% chance of being right. Not so hot.
Our First Attempt: 75% chance of getting saved
If the 1st prisoner says "pass", it means the 2nd prisoner's hat is black. They can guess correctly, and everyone else will pass.
Unfortunately, if the 2nd prisoner's hat is white, the 1st prisoner will have to guess his own hat color with 50% chance of success.
Therefore, there's a 75% chance overall that this strategy will be effective.
Our Final Solution
My wife came up with a solution that gives the prisoners a 1 - 1/2^n chance of being saved. Here it is:
Rule: If there are any black hats ahead of you in the questioning, pass. If there aren't, guess black.
This strategy will fail if everyone has a white hat. In that case, the first prisoner will incorrectly guess black and everyone dies. But it works for all the other possibilities. Here's why:
There's always going to be a "last" black hat in the questioning order (so long as there's a black hat at all). Using the strategy, everyone before this person will pass. Since this person is the last black hat, they can only see white hats ahead of them, so they will correctly guess "black".
With n people, there are 2^n possible assignments of hat color. Only one of these (all white hats) will fail with our strategy. Therefore, the chances of dying are 1/2^n. So the chances of living are 1 - 1/2^n.
No comments:
Post a Comment