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 every prisoner infinitely often. In other words, for any time, for every prisoner, there is a later time at which I will interrogate the prisoner.”

“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. Here’s your coin. 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. Do try to save their lives.”

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++: “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, and the hard version was created by me and solved by David Meierfrankenfeld and myself.)