Kominers’s Conundrums: The Warden Has a Brainteaser

(Bloomberg Opinion) -- Some puzzles are solvable in a blink. Others require deeper dives. The tale of the prisoners and the light switch is a classic brainteaser that takes several steps to unravel. Are you ready?

100 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 of a solution (along with 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 the 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

A perpetual energy paradox puzzle. You can turn colored pencils into a gigantic doughnut and/or subdivide certain right triangles into more right triangles. Try your hand at Roy Leban and Emily Dietrich’s Almanaq adventures, or this sudoku with only four given digits. Celebrate Sondheim’s birthday (hat tip: Ellen Kominers); dance with Tabla Maestro Sandeep Das; or watch a world-class Julie Andrews impersonator perform SuperBadTransmittableContagiousAwfulVirus. Explore Quanta Magazine’s map of mathematics, or just have some fun at home with dominoes. And inquiring minds want to know: Did supernovas really kill off the megalodon?

In addition to solutions, please send paradoxes, paraphernalia and/or your favorite puzzles to skpuzzles@bloomberg.net.

As in the one-room puzzle, the prisoners can confer beforehand to agree upon a strategy.

Admittedly, I took a bit of poetic license in the second line.

if you don’t see your name listed here, please don’t despair – we’re keeping track of all the solvers and will feature callouts to both new and recurring solvers as Conundrums continues.

Ross Berger came up with an alternate solution -- “CONTENT” -- which doesn’t fit the verse quite as well but isn’t too far off.

This column does not necessarily reflect the opinion of the editorial board or Bloomberg LP and its owners.

Scott Duke Kominers is the MBA Class of 1960 Associate Professor of Business Administration at Harvard Business School, and a faculty affiliate of the Harvard Department of Economics. Previously, he was a junior fellow at the Harvard Society of Fellows and the inaugural research scholar at the Becker Friedman Institute for Research in Economics at the University of Chicago.

©2020 Bloomberg L.P.