prisoner puzzle
"I have a puzzle for you" my fellow passenger asked....
I was riding on the last northbound Caltrain baby bullet train out of Mountain View at 6:38 pm, the one I've been taking pretty much every day since starting my new job last October. If I leave any later, I start paying the price of riding trains which make more stops, get me home even later. This is the latest train I can take and have time to eat dinner, relax a bit, and get a solid night's sleep before catching the 6:11 am southbound the next morning. Long days, sure, but I'm having fun.
"A jailer has too many prisoners in his prison and needs to get rid of 100. So he gathers 100 prisoners in a room. In an adjacent room he puts 100 hats, each hat containing one of the names of the prisoners, in random order. One by one, prisoners are brought into the room with the hats where they can pick from up to 50 hats (half) to find their name. If they find their name in those 50 picks, they leave through a back door into a third room separate from the first. If all one hundred prisoners find their names within 50 guesses, they all go free. If even one prisoner is unable to find his name, they all die. What strategy can they follow to maximize their chances?"
I and another passenger were listening to this, and we came up with ideas which would slightly improve the prisoners' chances. But each prisoner was going to have only a 50-50 chance or slightly better to pick his number. For one hundred prisoners to succeed would be like flipping a coin a hundred times in a row and picking heads or tails every time. That's a one in 2100 chance, which binary fans recognize as approximately 100010, which basically means the prisoners have no chance at all.
Yet he insisted they did have a reasonable chance. I struggled. I squirmed. The other guy proposed the prisoners each legally change their names to the same name, so then each of them would have their name in every hat, assuring victory. But then the puzzler wasn't buying that one.
"Think of permutations" he said.
But I just wasn't seeing it. "Suppose they were to do the following", I said, then described an approach. I was going to continue, "that clearly wouldn't work" but I didn't get that far.
"Yes. That's the answer!" he said, then he gave me the mathematically basis for the solution, which involved group theory.
No way. Simply impossible. It just didn't make sense to me. You can quote group theory all you want, but it wasn't going to change reality.
So today I tested it. I wrote a little Perl code to set up the game, then follow that strategy. I was stunned. Sure enough, first time I ran it, they won. So I set up the code to run the game 100 thousand times. The prisoners won in 29919 of these 100 thousand trials (losing in 70081).
Now the key is the first guy goes into the room, and no matter what scheme he devises, he can do no better than 50%. He's picking 50 hats out of 100 and thus has a 50-50 chance to win. Then he can't communicate in any way with the second guy, since he goes into a third room and the jailer is able to restore the hats to their original condition after the first prisoner has left. Yet clearly the second prisoner now has a better than 50-50 chance, if the first prisoner succceded, then the third prisoner has a still better chance if the second succeeded. Here's a chart showing the number of times the Nth prisoner is the first to lose:
In no case during the entire 100 thousand trials was any prisoner beyond the first twelve the first to fail.
So the reason the strategy works is it doesn't improve the chances of any one prisoner to succeed or fail. But it does mean if one fails, others will probably fail, and if one succeeds, others will likely succeed. By correlating results, my chances of succeeding with every prisoner increase, even if they don't increase for any given prisoner.
I won't describe the algorithm. That wouldn't be fair.
added As I lay in bed after submitting this post, suddenly everything gelled. It was crystal clear why the solution worked. There had been a few key points I'd missed. When I corrected those oversights, it seemed all so obvious.
I was riding on the last northbound Caltrain baby bullet train out of Mountain View at 6:38 pm, the one I've been taking pretty much every day since starting my new job last October. If I leave any later, I start paying the price of riding trains which make more stops, get me home even later. This is the latest train I can take and have time to eat dinner, relax a bit, and get a solid night's sleep before catching the 6:11 am southbound the next morning. Long days, sure, but I'm having fun.
"A jailer has too many prisoners in his prison and needs to get rid of 100. So he gathers 100 prisoners in a room. In an adjacent room he puts 100 hats, each hat containing one of the names of the prisoners, in random order. One by one, prisoners are brought into the room with the hats where they can pick from up to 50 hats (half) to find their name. If they find their name in those 50 picks, they leave through a back door into a third room separate from the first. If all one hundred prisoners find their names within 50 guesses, they all go free. If even one prisoner is unable to find his name, they all die. What strategy can they follow to maximize their chances?"
I and another passenger were listening to this, and we came up with ideas which would slightly improve the prisoners' chances. But each prisoner was going to have only a 50-50 chance or slightly better to pick his number. For one hundred prisoners to succeed would be like flipping a coin a hundred times in a row and picking heads or tails every time. That's a one in 2100 chance, which binary fans recognize as approximately 100010, which basically means the prisoners have no chance at all.
Yet he insisted they did have a reasonable chance. I struggled. I squirmed. The other guy proposed the prisoners each legally change their names to the same name, so then each of them would have their name in every hat, assuring victory. But then the puzzler wasn't buying that one.
"Think of permutations" he said.
But I just wasn't seeing it. "Suppose they were to do the following", I said, then described an approach. I was going to continue, "that clearly wouldn't work" but I didn't get that far.
"Yes. That's the answer!" he said, then he gave me the mathematically basis for the solution, which involved group theory.
No way. Simply impossible. It just didn't make sense to me. You can quote group theory all you want, but it wasn't going to change reality.
So today I tested it. I wrote a little Perl code to set up the game, then follow that strategy. I was stunned. Sure enough, first time I ran it, they won. So I set up the code to run the game 100 thousand times. The prisoners won in 29919 of these 100 thousand trials (losing in 70081).
Now the key is the first guy goes into the room, and no matter what scheme he devises, he can do no better than 50%. He's picking 50 hats out of 100 and thus has a 50-50 chance to win. Then he can't communicate in any way with the second guy, since he goes into a third room and the jailer is able to restore the hats to their original condition after the first prisoner has left. Yet clearly the second prisoner now has a better than 50-50 chance, if the first prisoner succceded, then the third prisoner has a still better chance if the second succeeded. Here's a chart showing the number of times the Nth prisoner is the first to lose:
In no case during the entire 100 thousand trials was any prisoner beyond the first twelve the first to fail.
So the reason the strategy works is it doesn't improve the chances of any one prisoner to succeed or fail. But it does mean if one fails, others will probably fail, and if one succeeds, others will likely succeed. By correlating results, my chances of succeeding with every prisoner increase, even if they don't increase for any given prisoner.
I won't describe the algorithm. That wouldn't be fair.
added As I lay in bed after submitting this post, suddenly everything gelled. It was crystal clear why the solution worked. There had been a few key points I'd missed. When I corrected those oversights, it seemed all so obvious.
Comments