Setup: 100 prisoners are being transported to a very special facility. While there, they will be kept in solitary confinement in 100 completely isolated rooms. There is, however, a "day room". Every morning, one of the prisoners is selected at random and spends the day in the day room. The only lasting effect a prisoner can have on the room is deciding whether to leave its single lightbulb on or off. The next day, whichever prisoner enters will see the light in whatever state the previous prisoner left it.
If a prisoner in the day room declares "We've all been in here by now!", then, if he's right and all 100 prisoners have been in the day room, everyone is set free. If he's wrong, however, everyone is killed.
The prisoners make an agreement and a plan. They agree that no one will say the magic words until they're *sure* that everyone has really been in the day room. But how can any prisoner ever be sure? They devise a plan to communicate using the single light bulb, so that way they can be sure that eventually someone will know.
The questions: What was a plan that would work? What's the plan that will get them all free in the shortest expected time?
Thoughts about the Solution:
Since we're slow thinkers, it took a good 15 minutes before anyone thought of any approach that would work. As it happened, I thought up the first idea, and although it "works", it would take several thousand years on average before anyone was sure.
Solution #1: Since this is prison, let's give all the prisoners numbers for easier accounting. We'll label them 1-100. Now, let's say all the prisoners are keeping track of how many days it has been since they reached the prison. This gives each prisoner a special day. Day 1, is prisoner 1's day. Day 58, is prisoner 58's special day. When we reach 100, we start over again. So day 1023, is prisoner 23's special day again.
Plan: A prisoner can only turn on his light if he enters the day room on his special day. Whoever enters the room the next day now knows exactly which prisoner was in the room the day before. He will then turn out the light again (if its not his special day). Eventually, some single prisoner will randomly be in the day room the day after all the other prisoners on their special days. Then he'll know everyone has been in the room, can say the magic words, and get everyone released.
You can see why this strategy will take a long time.
An improvement: Special windows
If I remember right, this improvement is due to our friend Nathan. His idea was: one special day is too short a time window to get randomly chosen to be in the room, and even after you're chosen, only 1 person will ever know what happened--the person who's in the room the next day.
So instead of one day, let's give everyone more days--a special "window" of days. Say, 10, for example. So now prisoner 1's special window are days 1-10. Prisoner 2's special window are days 11-20. Prisoner 58's special window are days 571-580.
Modified Rule: If a prisoner enters the day room any time in his special window, he turns on the light.
Before, only the prisoner on the day after would ever know what happened, because he would immediately turn off the light. Now the light stays on until the window ends--so everyone else who enters will know! If prisoner 1 enters the room on day 3, all the prisoners for the next 7 days will know that prisoner 1 was in the room!
Another nice feature of this idea, is that we have a parameter: the length of the window. If the window is length 1, then the solution is the same as before. A window of length 100 is probably too long because it would take 10,000 days just to make it through prisoner 100's special window! What's the optimal length for a window? We're not sure, but it's nice that you can systematically vary the window length to try and find out.
Another improvement: Rebroadcasting
This improvement, due to my wife Jen, is really a revolution. A problem with the old scheme is that if prisoner 72 knows that almost all the other prisoners have been in the room, he has no way of communicating that information to anyone else! He has to keep waiting to see the rest, or hope someone else does first. So let's modify the rule from the previous solution:
Modified Rule: You may turn on the light in prisoner n's special window of days if you are prisoner n, or if you know prisoner n has already been in the room.
This will let prisoner 72 act as a substitute or a proxy for the prisoners he knows have been in already so he can communicate that information!
Another improvement: Special "multi-prisoner" windows
Here is another idea (also Jen's) to allow faster communication about what a prisoner has seen. Let's say prisoner 72 knows that prisoners 1-50 have been in already. Even with re-broadcasting, he can't really communicate all this knowledge quickly through the single light. So let's add two more "special window" that come after prisoner 100's window before we loop back to prisoner 1's window again. The first window is the "prisoner 1-50 window" and the second one is "prisoner 51-100 window". Here's the rule for the new special windows:
New Rule: You may only turn on the light in a special window if you know all the prisoners represented by that window have already been in the room.
This means that if prisoner 72 enters the room during the first special window, he can turn on the light, since he knows prisoners 1-50 are covered. Then everyone else who enters in the special window will see the light on, and also instantly know that prisoners 1-50 have been in the room.
A different way to think about this is that it's a way of breaking the problem into smaller pieces. Rather than the 100-prisoner problem, you just have to solve 2 50-prisoner problems.
Notice that this improvement also contains a parameter: What size grouping of prisoners should each special window represent? Is it better to have 2 special window, each representing 50 prisoners? Or is it better to have 10 special windows, each representing 10 prisoners?
Totally Different Idea
The previous solution has become rather elaborate. Here's a different, very elegant solution (due to our friend I-Heng):
Plan: Designate 1 prisoner the "collector". Only he may turn off the light in the room. Every other prisoner will turn on the light exactly once. Once the collector has turned the light off 99 times, he may safely conclude everyone has been in the room.
Clean, eh?
Concluding Thoughts
Clearly we've found lots of different types of solution. Which is the best? Which gets the prisoners out in the least expected time? We've had difficulty answering this question, because some of our improvements to the original idea made it very hard for us to figure out what the expected time to release is! There has been some discussion of writing computer simulations of the strategies and running millions of trials to find out, but no one has really wanted to do this yet.
If you've thought of other ideas or have done expected time-to-release calculations, we'd love to know!
No comments:
Post a Comment