Justin Pombrio

The Prisoners' Lightbulb

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

“I hear you’re real clever,” says the warden. “Quite the mathematician. Well, I’ve got a conundrum for you. I have 143 prisoners, not counting you of course. I’m going to interrogate them, one by one. I’ve made a long list – infinitely long, in fact – and each prisoner appears on it infinitely many times. I’m going to go through the list in order, fetch the indicated prisoner from their cell, interrogate them, and return them to their cell.

“The cells in this prison are quite isolated. No one is going to be able to tell when or how often I interrogate anyone else. When I interrogate someone, I will always ask the same 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 someone says ‘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.

“Now of course 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. I’m kind, so I’ll let you know that 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 everyone.

“I should mention that I will interrogate the prisoners in every possible order. That is, for every possible sequence of prisoners, and for every possible time, there is a later time at which I will interrogate the prisoners in exactly that sequence.”

“So, figured it out yet? Here’s the intercom. It goes out to every prisoner. When you’re ready, tell them what I’m up to, and what their strategy should be. You’ve got all night. I’ll start the interrogations tomorrow, or maybe later, depending on my mood.”

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

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

Easy++: “Oh, I almost forgot to mention. I reserve the right to flip the light on or off between interrogations up to 12 times in total.”

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. Do try to save their lives.”

Hard++: “Oh, I almost forgot to mention. I reserve the right to flip the light on or off between interrogations up to 12 times in total.”

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.