Setup: There are n prisoners standing in a line, facing front. The executioner starts at the back of the line and randomly gives each prisoner a black or a white hat to put on. No one can see their own hat color or the hat colors of anyone behind them, but they can see all the hats of the people in front of them. The executioner will walk down the line starting from the back and ask each prisoner to guess their own hat color. Each prisoner can only say "black" or "white". If they guess right, they will be set free at the end. If they guess wrong, they will be killed at the end. The prisoners realize that by saying "white" or "black" they can try and communicate information to the prisoners in front of them that might help the others guess their own hat colors right.
Question: What strategy can the prisoners use to save as many of themselves as possible? How many can we expect to save?
* * *
(Too) Easy Solution ("Cheater Solution")
You can easily save everyone except the first person like this: No matter what a prisoner says, if they say it in a high, squeeky voice, that tells the next prisoner their hat is white. If they say it in a deep, low voice, that tells the next prisoner their hat is black. Now everyone (except the first person who still has to guess) has been told their hat color by the tone-of-voice of the previous prisoner.
This was the solution one of my students thought of. It clearly works, and we shouldn't turn up our noses at a creative solution that works. But the puzzle is deeper then that, and will yield interesting things if we disallow this type of solution.
So, let's say that there is no communicating in sneaky other ways: each prisoner only hears one bit of information--"black" or "white" with no additional information.
First Attempt
Since we always start with the most obvious thing we can think of, here it was!
Rule: Each person should say whatever hat color the next person has on.
How does this rule fare? The first person helps the 2nd person go free, and has a 50% chance of being right about themselves. But since the second person will say their own hat color (to go free), they can't also tell the next person what their hat color is. Since the 3rd person can't be helped, they'll help the 4th person go free by telling them their hat color, and only have a 50% chance of being right about themselves. In general, every odd numbered person will say the hat-color of the next person in line, with a 50% chance of being right about themselves. Every even numbered person will be told their hat color by the prisoner behind, and so will have a 100% chance of survival. All together we should expect to save about three quarters of all the prisoners with this strategy.
This seemed ok, be we thought we should be able to do better.
What Makes it Hard
The problem with our 1st solution seems to be a problem with *any* solution. Whenever a prisoner knows their own hat color, they have to say it to go free; but in that case they can't also be communicating information to the other prisoners since they can't base what they say on what they see--that have no choice about what to say if they want to go free.
Solution
This solution can guarantee that everyone is saved except the first prisoner who has a 50% chance.
Rule: 1st prisoner says 'black' if he can see an odd number of black hats. He says 'white' if he can see an even number of black hats. The other prisoners deduce their own hat colors, and say them.
Here's how this works. The 1st prisoner and the 2nd prisoner can both see all the others. Whether or not a number is even or odd is called its parity. If the 1st prisoner and 2nd prisoner see a different parity of black hats, the 2nd prisoner knows that his hat must be black. If the 2nd prisoner's hat were white, then he and he 1st prisoner would see the same number of black hats.
Therefore, the 2nd prisoner will be able to say his own hat color correctly by checking if the parity of black hats he sees is the same as what the 1st prisoner said or not. The 3rd prisoner heard what the 1st prisoner said about the hat parity, and knows that the 2nd prisoner said the true color of his own hat. With this information the 3rd prisoner can deduce his hat color in the same way the 2nd prisoner did, and say it correctly. This reasoning continues down the line to the very last prisoner and they are all saved.
This solution gets around what seemed to make the problem hard because the parity of black hats seen by the first player depends on the state of all the other hats. When each prisoner says their own hat color correctly, they're also giving information to the later prisoners: namely, what their hat colors actually are. The later prisoners use this information, combined with what the first prisoner said, to figure out their own hat color.
A Different Way To Look At It
Here's a different way to look at it. The way each prisoner figures out his own hat color is by solving a simple equation of modular arithmetic.
First, let's give all our colors numbers.
white is 0
black is 1
Lets record each prisoner's hat-color in a variable. The 1st prisoner is p1, the 2nd prisoner is p2, and so on.
The 1st prisoner says the parity of the number: p2 + p3 + p4 + ... + pn
Another way to describe the parity of a number is as its remainder when divided by 2. If you divide a number by 2 and get remainder 0, you know the number was even. If you divide a number by 2 and get remainder 1, you know the number was odd.
The conventional way to write the remainder of a number S when divided by 2 is: S mod 2
Just to make sure you understand. Say W = 53. What's W mod 4?
It's the remainder left over when you divide W by 4. Since W = 53, W mod 4 is 1.
With that in mind:
Let's call the parity of black hats the 1st prisoner can see, S. In other words:
S = (p2 + p3 + p4 + ... + pn) mod 2
Let's call the parity of black hats the 2nd prisoner can see, T. In other words:
T = (p3 + p4 + ... + pn) mod 2
Player 2 knows that:
The parity of the hats player 1 sees = his own hat parity + the parity of the hats he sees
In other words:
S = (p2 + T) mod 2
The only thing he doesn't know in this equation is p2--his own hat color. He can figure it out by solving the equation.
This seems more complicated, but is the key to generalizing the solution later.
No comments:
Post a Comment