23 Clones and Two Lightbulbs

Question

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 1

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.)

Answer 2

The standard solution is that all clones signal their first passage using some state of the bulbs to an elected clone, the "counter", who counts how many there are.

You need to address 3 things.
1. How to transmit the information of one's passage reliably,
2. How to deal with the initial state,
3. How to elect a counter.

Note that the lights don't represent the "state of the room", but represent a message that a clone can pass to whichever clone following him. The message consists of 2 bits of information.

(1) is pretty easy. Each clone has a virtual token. He must pass this token to the counter. Any clone might have multiple tokens in his possession at any time.

Assign to the blue light the meaning "I give you one token". A clone who finds the blue light on automatically increases his token count. If he wants to get rid of a token, he leaves the blue light on before leaving and decreases his count.

The counter will collect all tokens and never leave the blue light on, all others will push their tokens to the next clone by leaving the blue light on. That is, if they still have one.

For (2) we need to adjust the method. The blue light might be on initially. The first clone, not knowing he is first, will count this as a token. Therefore the total token count is actually 23 or 24, and the counter doesn't know when to declare the end of the game.

To overcome that problem we need to double the number of tokens. Every clone starts with 2 tokens. Then the total number of token is 46 or 47 and the counter can safely declare the end as soon as he has collected 46 token.

For (3) we need to settle for a single counter. But make sure there is at least one. This can be achieved with the red light. Every time a counter visits the room he toggles the red light. But if he sees that the red light has changed state in his absence, that means here is another active counter. If that happens, he simply resigns his role without changing the red light. He will spend the rest of his time as a non-counter getting rid of any token he already collected. With time only one counter should remain.

So, in fact, all clones start as a counter. On the first passage they collect any token they get, don't leave any, and switch the red light. Starting with the second passage, they will check the red light and possibly become a non-counter.

So the method is as follows:
- the initial state of each clone is the role of counter with 2 token.
- any clone seeing the blue light on when arriving, increases his token count.
- a counter with a token count of 46 declares that all clones have been in the room.
- a counter who sees that the red light changed becomes a non-counter. He acts as such in the 2 last rules.
- a counter who remains a counter always toggles the red light. All others leave it unchanged.
- a non-counter with non-zero token count switches the blue light on and decreases his count. All others switch the light off.

There can be optimizations, for example, a counter with at least 24 token doesn't change role any more. Or on its first visit, if the the blue light is off, you directly become a non-counter. But the more you optimize the less certain it is that the solution works...

Answer 3

Who even needs multiple bulbs? Let's solve this using just the red bulb!

Each clone maintains a personal count C, which starts at 0.
Ignore the state of the blue bulb. The red bulb is on or off; Let "on" be L = 1 and "off" be L = 0.

If L = 0, 22 > C > -2: set C = C-1, L = 1
If L = 0, C = -2 or C > 21: do nothing
If L = 1, C < 43: set C = C+1, L = 0
If L = 1, C = 43: declare that all clones have entered the room

Logic behind this:

Each clone sets L = 1, and C = -1 to vote. The next clone to enter will set L = 0 and C = 1, collecting the vote. The same clone seeing the room multiple times in a row will just keep redoing and undoing the same two actions. As a result, +1 and -1 are always conserved, but will be redistributed at random until eventually some clone gets lucky and happens to collect a lot of votes. Note that no clone can ever go further than -2 through this process, so each clone has at most two votes. Confusion about the initial state means that when one clone manages to collect all the votes, there will be either 44 or 45 votes to collect - but as long as they collect at least 44, then everybody has voted once, since 21 other clones would cap out at 42 or 43 votes. Since every finite pattern will appear in an infinite random pattern, we simply need to know that there exists a pattern that causes 44 votes to be gathered by one clone.

The pattern, of course, is (starting when L = 0), Clones enter the room in this order: 2 - 1 - 2 - 1 - 3 - 1 - 3 - 1 - 4 - 1 - 4 - 1... etc. Clearly this can transfer all votes to 1, thus it will eventually happen with probability 1. The > 21 case just means that as soon as a clone gets half the votes, they can stop giving them back. (If some votes have already been distributed, clones will simply show up in the above sequence once for each increment their counter is above -2)

---

For posterity, my old solution, using both bulbs and a designated counter

---

Each clone maintains a personal count C
The combination of lights have four positions, L = 0, 1, 2, 3 – initial state unknown
Clones distinguish between their first visit to the room and subsequent visits

First visit:
If L = 0: set C = 0, L = 0
If L = 1, 2, or 3: set C = 1, L = 0

Subsequent visits:
If L = 0, C > -1: set C = C-1, L = 1
If L = 0, C < 0: do nothing
If L = 0 and you are TCO: declare that all clones have entered the room
If L = 1, C < 21: set C = C+1, L = 0
If L = 1, C = 21: set C = 0, L = 2: you are The Chosen One
If L = 1 and you are TCO: declare that all clones have entered the room
If L = 2 and you are TCO: do nothing
If L = 2 and you are not TCO and C != -2: set C = -2, L = 3
If L = 2 and you are not TCO and C = -2: do nothing
If L = 3 and you are TCO and C < 21: set C = C+1, L = 2
If L = 3 and you are TCO and C = 21: declare that all clones have entered the room
If L = 3 and you are not TCO: do nothing

Logic behind this:

If L = 0 initially, every clone initializes to C = 0 until a clone enters for a second time. This clone has C = 0, so they set L = 1, and C = -1. The next clone to enter will set L = 0 and C = 1, whether it's their first time or not. At this point, nothing happens for a while again until a clone enters for the second time, and sets themselves to -1 and another clone to +1. The same clone seeing the room multiple times in a row will just keep redoing and undoing the same two actions. As a result, +1 and -1 are always conserved, but can be redistributed until eventually some clone happens to collect a lot of +1s without any -1s. Note that no clone can ever go further than -1 through this process, so no clone is being double counted. At some point, a single clone will hit C = 22 as a result. But this is where the initial state becomes an issue.

This clone doesn't know if the initial state was 0, so there are 22 other -1 clones and just them as a +22 clone... or if the initial state was 1, 2, or 3 and there's an extra +1 from the very first clone that's not balanced out anywhere else - giving only 21 other -1 clones, themselves as a +22 clone, and one clone that's at 0, or has never visited the room.

At this point, this clone knows they are very close, so they declare themselves The Chosen One, and set L = 2 while resetting their count. If a clone has already been in the room before, this is the only way they could see an L = 2, since initialization and early moves only give L = 0 or L = 1 past the very first clone. If every clone has been in the room before (initial state was 0), this is a subsequent event for all of them, and they know that it's special. The first one to receive this message responds with a 3 (meaning "count me!") and then removes themselves from the game. One this gets to The Chosen One, they count and reset to 2. This continues until everybody responds with 3, at which point The Chosen One will get to a count of 22 again and declare victory. Alternatively, the initial state was not L = 0. In this case, there is one clone who isn't at -1. If they're at 0, they count from 2 to 3 like everybody else, and The Chosen One still gets to 22. If they hadn't been in the room at all before, they go from L = 2 to L = 0, and set C = 1. At this point, a lot of stuff can go weird with the counts due to them entering the room consecutively (setting it to L = 1) and then other clones who hadn't seen the L = 2 case doing stuff, but it all boils down to one thing - nobody can get up to a count of 22, because there is at most a +1 in the system. Therefor there can never be a second Chosen One, and nobody can ever set L to 2 or 3. As a result, whenever The Chosen One returns to the room, L = 0 or L = 1 - either way, this can only have been caused by the last missing clone showing up and screwing around. At this point, all the clones are accounted for, so The Chosen One declares victory without finishing the count.

Answer 4

Here's my solution. Took me awhile to figure out, and I'm not 100% sure it's right, but I believe it is:

Each clone starts off in an "uninitialized" state. In that state, when they go into the light bulb room they will look at the lights. If the lights are both off, they will move to the "counter" state and turn both lights on. Otherwise, they will move to the "peon" state with a value of 1 and turn both lights off.

A peon's job is simple: If he sees two light's in the up position and has a value above 0, turn blue off (leaving only red on) and decrease his value. Otherwise, don't do anything.

A counter can enter the room in one of 4 positions: 0, red, blue, or 2 lights on. If both lights are off, he turns them both on. If only the red light is on, he adds 1 to the number of clones he's counted, then turns both lights on. If he sees 2 lights on, he turns off the red light (leaving just blue on). If he just sees the blue light is on and he set it that way last time he was there, he turns both on again. Otherwise, he knows there must be another counter who set it that way, so he turns into a peon with a value equal to his count (+1 for himself).

Over time, this should converge until one counter has seen a single response per clone and knows that they've all gone.

I appologize for the bad grammar/formatting, it's late and I'm tired. If someone else doesn't get to it I'll edit tomorrow.

Answer 5

This is fascinating because it's basically a multi-threaded programming problem with interesting restrictions.

So I wrote the first answer by Zerris in JS and executed it. The function looks like it always passes but takes anywhere up to 5 million loops (around 100k minimum). Unless I implemented it wrong, I based it on the four-case scenario (three technically since the 2nd case does nothing). I didn't test his multi-light answer and it may be much cheaper than the single-light answer.

I wrote my own answer in which each user acts as its own counter and waits for itself to count 23 observances of fourth state enum(where: off=1, red, blue, blue & red) and each clone adds +1 to the state (mod 4 to reset it). It's not guaranteed to pass, however it has a high success rate (I don't know what it is statistically, but it's not 'guaranteed' to pass). And takes anywhere up to 2000 loops (around 1100 minimum) which is several order-of-magnitudes cheaper than the single-light answer.

I sort the arrays at the end to show their individual counts.

I Added his 2-light solution as well to the jsfiddle. I also had to modify it similar to his single-light that at some point the counters stop returning their counts if they exceed a certain value, else it runs into an infinite loop in MANY cases.

However, I found that it performs about the same (I also prevent it from exceeding 2million iterations because it usually ends up in that near-infinite case) as the single-light. It appears to have lost efficiency in adding another needless state compared to his newer answer since it runs about the same amount of iterations to succeeed but also seems to be less guaranteed than the single-light solution.

https://jsfiddle.net/u3nnp68s/2/

I believe this means that there must be a cheaper way than the Zerris' single-light (and 2-light) answer to "statistically guarantee" a pass/fail for n-clones. I would be interested to see what solution offers the highest success rate with lowest iterations would be.

Answer 6

We want to reduce this problem to a single light bulb problem and assign a "counter clone". When we achieve this, we're done.

To get rid of one light bulb, the only way we can do this within the rules of the game is to make sure it is switched on or off a lot of times. This will in the end break the light bulb.

So every clone will go in with the following instructions:

• Go into the room and check the blue light bulb.
• If it is on --> switch it off and if the red bulb on, switch it off as well (This to make sure we conserve it). Then your done.

• If it is off -->

  • Try to switch it on, if it works the blue light bulb is still not broken. If the red bulb is on, switch it off (conserving it) Then your done
  • Try to switch it on, if it does not work another clone has broken it already and you can continue to the red bulb.
  • Try to switch it on, if you see the blue bulb give one light flash, you're the clone breaking the blue bulb. You are the "counter clone" and can continue to the red bulb.

• At the red light bulb, the "counter clone" will always switch the bulb on and count the number of times he finds the red bulb off. If he finds the bulb off 22 times, everybody has visited the room and he can make the declaration.

• The other clones will switch the red bulb only off the first time they find it on. All the times they visit the room after their first time, they do nothing.

This strategy might take long, because it might take some time to break the first light bulb. But this strategy will provide certainty.

Answer 7

The clear answer is that James actually has no chance of success. Like all supervillains, the designer of this machine is obsessed with overly dramatic methods of killing people; they merely want to watch James think himself into a tizzy and then voluntarily walk into a machine that will vaporize him.