Dartblog

I trust you have been busy thinking away at my puzzle of the prisoners and the lamp? Have you come to a solution? Mine is below. First, a recap.

One hundred prisoners yearn for freedom. Each day one of the prisoners, picked at random, is escorted to a room with a lamp. There, the chosen prisoner can do one of three things: 1. nothing; 2. toggle the on/off state of the lamp; or 3. announce that all 100 prisoners have visited the lamp room. As soon as one of the prisoners makes the announcement, all the prisoners are freed if it is correct and killed if it is wrong. On the morning of the first day, the lamp is off. What strategy can the prisoners use to guarantee their freedom? (They have some time to discuss before the process begins.)

On its face the task seems impossible. To guarantee that the prisoners “win,” they must be certain at the time they make the announcement that each has visited the room—completely certain. How can 100 prisoners communicate amongst each other using but a single bit of information? (That is what the lamp is, really—a binary digit. Compare a brief paragraph of text, which takes thousands of bits to encode.) Worse, only a single prisoner at a time has access to the state of the bit! If one prisoner toggles the lamp switch, how will all the other prisoners know?

There are two essential insights. The first is that the prisoners actually have much more at their disposal than just the lamp, and they have vastly more information than can be conveyed through the lamp. They have their memories. Each prisoner knows how many days have passed, and each remembers whether he was chosen on each day, and if so, what he did in the lamp room.

The second essential insight is that for the prisoners to win, they don’t all have to know that they have all visited the lamp room. Ninety-nine of them can have no idea what’s going on. It is good enough for a single prisoner to be certain that all have visited the room—so long as that prisoner is the one to make the announcement.

In view of these insights, here is my solution.

The prisoners designate one among them to be the counter; all the rest shall be illuminators. When an illuminator is taken to the lamp room, he acts as follows: If the lamp is off and he has never before turned it on, he turns it on; otherwise he does nothing. When the counter is chosen, he acts thusly: if the lamp is off, he does nothing; if the lamp is on and he has not yet turned it off 98 times, he turns it off; otherwise, he makes the announcement. That is to say, on the 99th time that the counter enters the room to find the lamp illuminated, he makes the announcement.

The proof that this is a solution is simple. Each illuminator registers that he has been to the room by turning on the lamp if it is off. The counter counts, and turns off the lamp so that the remaining illuminators can take a turn. Each illuminator only ever touches the lamp once, to turn it on. Therefore when the counter has seen the lamp on 99 times, it was illuminated each of those times by a different illuminator. That means all of them have visited the room. And of course, the counter has been to the room (at least 99 times).

How long will it take?

Let’s calculate the expected number of days my strategy will take to free the prisoners. That’s basically a fancy way of saying the “average” number of days. As I explained here, it is not possible to specify a maximum number of days.

Consider the “structure” of my solution. Before the counter makes the announcement, a sequence of 198 events must occur. First, one of the illuminators must turn on the lamp. Second, the counter must turn it off. Third, another illuminator must turn it on. Fourth, the counter must turn it off. And so on.

Each of these steps takes some number of days. How many days? Well, we can’t say, because of the randomness of the game. But each step has a distribution describing the number of days it might take. These distributions are mathematically nice, (they are called geometric distributions), and it is easy to calculate their expected values individually.

There is an extremely excellent fact about expected values that the expected value of a sum of distributions is the sum of their expected values. This gives a nice way to break down the problem. We just need to calculate the expected number of days for each individual step, and then add them up! Also, all the even-numbered steps have the same distribution, because the same thing needs to happen at each of them—the counter turns off the lamp. So their expected values will be the same.

The expected value of the number of tries (days) it takes to choose one particular object (the counter) randomly out of 100 objects is, surprise surprise, 100. So the counter’s 99 steps take a total of 9,900 days in expectation.

The odd-numbered steps, when an illuminator must turn on the lamp, take more and more time (in expectation) as the game progresses, since there are fewer and fewer acceptable illuminators remaining, so it is less likely that one will be chosen on each particular day. In general, though, the illuminators’ steps are much faster than the counter’s.

In expectation, the illuminators’ steps take a total of

1/.99 + 1/.98 + 1/.97 + … + 1/.03 + 1/.02 + 1/.01 = 517.74 days.

So the expected number of days before freedom is 10,417.74, which works out to just over 28 1/2 years. Not bad.

When I presented the puzzle, I asked as a corollary question if it would be possible to save the prisoners with certainty if the initial state of the lamp were unknown. The answer is yes, of course it is. Don’t overthink it. Modify my above solution as follows. The prisoners do not assume their roles until the second day. On the first day, no matter which prisoner is chosen, illuminator-to-be or counter-to-be, the chosen prisoner turns the light off if it is on, or leaves it off if it is off. Then, starting on the second day, the game progresses as usual.