Rise and shine, Mister Bond.
James awoke to find himself yet again imprisoned by an evil genius. At least, that's what he presumed. He was alone in a room with a strange device: it consisted of a person-sized glass chamber, with a single tube feeding out of it, splitting into 23 tubes which headed God knows where.
I do hope you're comfortable, since you will be here for quite a while. We're going to play a little game.
The voice was coming from an intercom. "If it's information you want, you might as well kill me. I'll die before I tell you anything!"
Nothing so routine, Mister Bond. What I want is to test your mettle. The device in front of you is a cloning machine: it will completely vaporize your body, but will create 23 identical copies in your place, each to be housed in separate prison cells.
After this I will, at random times, bring a random clone out of his cell into the Light Bulb Room. This room has two lightbulbs, one red and one blue, which are each either on or off. The clone may then toggle none, either or both of the bulbs, before I return him to his cell. I will take care to ensure the clones can't communicate with each other, or change the Light Bulb Room in any other way then toggling these bulbs.
"And what exactly am I supposed to accomplish through all this?"
A clone may at any time make the declaration that every clone has visited the Light Bulb Room room. If he is right, you win and may all go free. If he is wrong, you will all be executed.
I'll give you some time to think of a plan before this begins. Since my machine copies your brain state exactly, all of the clones will follow the exact same plan.
Time to see if you really are the stuff of legends, Mister Bond.
"Wait! What did you say the initial states of the light bulbs were?"
I didn't.
A faint crackling, then silence.
How can James Bond succeed, with certainty?
Compare and contrast this with the classic "100 prisoners and one lightbulb" puzzle. In that one, the prisoners could use an asymmetric strategy where one prisoner was singled to count the others. This asymmetry is now ruled out since all prisoners are clones. The winning strategy will require the extra power of having two light bulbs.
Answer
This puzzle is isomorphic to one given each year (at least back in the early 2000s) by Steven Rudich in Carnegie Mellon's course 15-251 "Great Theoretical Ideas in Computer Science." That puzzle was traditionally described in terms of "bunnies on a see-saw." Spoiler below:
We have 23 bunnies. Each bunny can be in one of three internal "locations": either it is at home asleep, or it is at the playground, or it is at the malt shop. Also, each bunny has two pebbles.
The playground is where all the bunnies come during the day. At the playground there is a see-saw big enough for all the bunnies to pile on. In the center of the see-saw is a small cup. We'll refer to this as the "pebble cup."
Did I mention these bunnies are narcoleptic? They may randomly fall asleep from time to time. In fact, only one will be awake at any given moment. But they do remember where they are, and they can observe the state of the playground while they're awake. Namely, they can observe the orientation of the see-saw, and they can observe whether there is any pebble in the pebble cup.
The first time a bunny wakes up, he leaves his house and goes to the playground. (There may or may not be other bunnies already at the playground. He won't be able to see them.) He gets onto the see-saw (at the low end, of course) and pushes off the ground so that the formerly low end of the see-saw is now the high end, and vice versa.
Since every bunny follows this procedure, the result is that the see-saw is always balanced: either there's an equal number of bunnies on both ends, or the high end has exactly one more bunny than the low end.
When a narcoleptic bunny awakes already on the see-saw, he looks to see whether he's on the high end or the low end. If he's on the high end and there's no pebble in the pebble cup, he puts one of his pebbles into the cup. If he's on the low end and there's a pebble in the pebble cup, he takes that pebble.
Since every bunny follows this procedure, the result is that pebbles "flow downward" from the bunnies on the high end of the see-saw to the bunnies on the low end.
When a bunny places his last pebble in the pebble cup, such that he has no more pebbles at all, he's done playing for the day. He lowers his end of the see-saw to the ground and dismounts and goes to the malt shop, where he stays quietly for the rest of the day and drinks milkshakes.
Since every bunny follows this procedure, the result is that the see-saw is always balanced: either there's an equal number of bunnies on both ends, or the high end has exactly one more bunny than the low end.
After each bunny has woken up a large but computable-and-finite number of times, the second-to-last bunny places his last pebble in the pebble cup, dismounts, and goes to the malt shop. This leaves the final bunny on the high end of the see-saw and in possession of at least 2×23 = 46 pebbles. (Possibly 47, if there was a random playground pebble in the pebble cup originally.) At this point, the final bunny sees that he's got 46 pebbles, and therefore knows that everybunny has visited the playground. Therefore he can go to the malt shop too, and announce confidently that every bunny has been awakened.
The shared memory state is 1 bit for the see-saw (is the left side low and the right side high, or vice versa?), plus 1 bit for the pebble cup (is there a pebble in it, or not?). The initial state of the bits doesn't matter.
The local, non-shared memory state of each bunny is lg(N) bits to count how many pebbles they own, plus lg(3) bits to indicate whether they remember being on the left side or the right side of the see-saw or whether they just woke up and aren't on the see-saw yet. (They don't need a bit to indicate that they're in the malt shop, because a bunny is in the malt shop if-and-only-if he owns 0 pebbles.)
The solution scales up or down to any number of bunnies, including 1 bunny. (If there's only one bunny, then he immediately finds himself on the high end of the see-saw in possession of 2×1 = 2 pebbles, and goes straight to the malt shop and make the announcement to himself.)
No comments:
Post a Comment