Justin Pombrio

The Prisoners' Lightbulb

One day a logician finds himself in the hands of a prison warden.

“I’m a villian”, says the Warden to the Logician. “I am therefore honor bound to explain my evil plan to you in great detail, and to leave some way for you to save the day. This I will do, but I’m only giving you a night to think on it, and you surely won’t find the solution in time.”

“The first phase of my plan is already complete. I have captured all the other logicians in the galaxy, all 143 of them. I have wiped their memories: none of them remembers their name or any other fact about themselves, though they remain perfect logicians. The prison is perfectly sealed: there are no windows or clocks, and no prisoner can ever tell or accurately guess what time it is. The cells, and the single interrogation room, are all perfectly isolated: no prisoner will ever see, hear, or otherwise sense any other, even if they are interrogated one after the other.”

“Next begins phase two. I will interrogate the prisoners. To be fair, I will interrogate every prisoner infinitely often. And furthermore, for every possible sequence of prisoners, I will eventually interrogate those prisoners in exactly that sequence.”

“I can tell you’re wondering what an interrogation looks like. Well, first I fetch the prisoner from their cell. Then I ask them a simple question: have I interrogated all of the prisoners at least once? Acceptable answers are ‘I don’t know’, and ‘yes, I’m sure we’ve all been interrogated’. If the prisoner says ‘I don’t know’, I’ll simply return them to their cell. On the other hand, if they say ‘yes’ and they’re right, I’ll let everyone go free. But they’d better be certain, because if they’re wrong I will execute everyone. You would of course never pick a solution in which this is ever a possibility, however unlikely.”

“Now obviously this is impossible with no means of communication. So I’ll put a single lightbulb in the interrogation room, and let whoever’s in the room flip it on or off if they like. It starts turned off. No cheating, by the way – if I catch anyone using any means of communication other than seeing whether the light is on or off, I will execute all of the prisoners.”

“Your goal, of course, is to find a strategy that is guaranteed to eventually release all of the prisoners. Once you think you have one, you may speak over this intercom. It goes out to every prisoner simultaneously. When you’re ready, tell them what I’m up to, and what their strategy should be. You’ve got all night.”

“There’s just one thing you haven’t told me,” says the Logician. “Will I be among your prisoners?”

Easy: “Yes; with you I’ll have 144 in total. You will play by the same rules as everyone else, though I won’t erase your memory. I’ll show you to your cell after you speak over the intercom.”

Hard: “No. I have 143 prisoners and you’re not one of them. I’m going to release you as soon as you speak over the intercom. You’ll have no contact with any prisoner after that.”

This is a variant of the prisoner lightbulb puzzle. The Easy version is the regular puzzle, which you may have seen elsewhere. The Hard version was created by me and solved by David Meierfrankenfeld and myself. It is much harder than the standard puzzle.

(Note: this puzzle is from 2015; I reposted it in 2020.)

January 25, 2020