By Scott Duke Kominers, Bloomberg Opinion

SOME puzzles are solvable in a blink (https://www.youtube.com/watch?v=0SWgSZdSBjc). Others require deeper dives (https://www.bloomberg.com/news/articles/2020-03-27/eyos-submarine-dive-to-challenger-deep-bottom-mariana-trench). The tale of the prisoners and the light switch is a classic brainteaser that takes several steps to unravel. Are you ready?

One hundred people are being held prisoner. The warden, who is slightly benevolent — and also a mathematician — proposes to have the prisoners play a game in exchange for their freedom. He shows them a room with a single light switch, and explains: “Each day, I’m going to choose one of you at random and bring you into this room. When the first prisoner walks into the room, the switch will be ‘off.’ While you’re in the room, you can flip the switch if you want, and I’ll leave it however you set it for the next prisoner. Any one of you can declare at some point that all the prisoners have been in the room at least once; if you’re right, all of you go free; and if you’re wrong, you stay here until I come up with an idea for a new puzzle!”

Being bizarre, but fair, the warden lets the prisoners confer beforehand to agree upon a strategy — but once the game has started, the prisoners have no way to communicate except (possibly) by flipping the switch.

Can you figure out a strategy that guarantees the prisoners their freedom?

The word “guarantees” is important in this puzzle: It means that the full solution is not just a strategy the prisoners should use, but also a logical argument (a “proof”) convincing us that the strategy will work for every sequence of room entries that might arise.

(If you want to try the problem yourself without any hints or guidance, stop reading here for now.)

So how to even start figuring this out? First, try making the problem smaller. If there’s only one prisoner, they can just declare victory upon entering the room for the first time. If there’s two, the problem becomes more subtle: Each prisoner knows when they’ve been in the room, but nothing else.

(Again, perhaps pause here and try to work it out for yourself.)

But what if the prisoners decided beforehand that one would flip the switch as soon as he or she entered the room while the other would merely wait until that happened? This strategy might take a long while to work. But there’s no time limit in this game. At some point, the first prisoner will enter the room, and sometime after that, the second prisoner will enter and learn that the first prisoner has already been there.

This is- the first major logical leap in solving the puzzle: Prisoners can have different roles.

So what happens with three prisoners? And can we get from saving three prisoners to 100? Brett Berry of Math Hacks has a beautiful write-up (https://medium.com/i-math/100-prisoners-and-a-light-bulb-573426272f4c) of a solution (along with a slightly different approach to solving).

For a modern — and very nearly post-modern — version of the puzzle, here’s one from my personal vault. In 2008, Paul Kominers (my brother), Justin Chen and I asked what happens when the warden gets a prison so large it feels like something out of a Greek myth:

Now the warden has a labyrinthine prison with 111 indistinguishable rooms, each of which has the same number of light switches in them — and all the switches in all the rooms start “off.”

He’s going to lead his 100 prisoners into the rooms at random (one at a time, like before) and the prisoners win their freedom if — and only if — one of them correctly declares that each prisoner has been in each of the 111 rooms at least 17 times each.

The question is: How many switches do the prisoners need to have per room in order to find a strategy guaranteeing them their freedom?*

As before, the solution will involve developing a strategy and a proof that the strategy works. But now there’s the additional wrinkle that you can adjust the number of switches to make the game easier or harder for the prisoners.

Give it a try. We’ll go over the solution next week.

In the meantime, if you come up with something — even partial progress — please let me know at skpuzzles@bloomberg.net before midnight EDT on Wednesday, April 29. (If you’re stuck, there’ll be a hint announced in Bloomberg Opinion Today on Tuesday, April 28. Sign up here.)

LAST WEEK’S CONUNDRUM
The Fudd was the word. Our foray into wordplay included two puzzles challenging readers to fill in the blanks with words that are spelled the same way but have different meanings. First, we were “BEFUDDLED” that any hunter would want to “BE FUDD-LED” — Elmer Fudd from Looney Tunes never quite manages to catch the wascally wabbit, irrespective of whether it is rabbit or duck season.

Then, I challenged you to find a seven-letter word that could fill in both blanks in a second verse:

Stuck at home another week:

a child past SEVEN?

“Not at all,” he said to me,

“I’ve got my game SEVEN!”

In total, 13 people came up with the intended solution, “CONSOLE.”** Zoz and James Flynn were first — within minutes of each other, and less than two hours after the column hit the web. Other solvers (selected randomly***) included Matthew Dickstein, Nancy Glaeser, Alex Newman-Smith, and Rianne Rowlands.****

THE BONUS ROUND:
MORE PUZZLES AND PASTIMES