Home Arts & Leisure Kominers’ Conundrums: There’s a puzzle hiding in this column
Kominers’ Conundrums: There’s a puzzle hiding in this column
By Scott Duke Kominers, Bloomberg Opinion
YOU’VE already unraveled brainteasers and played with words. This week’s Conundrum is a bit mysterious.
There’s a puzzle hidden in this column — the one that you are reading right now — but there are no instructions as to how to find it, or how to solve it. This format transforms the experience of solving into something like a treasure hunt.
How to start? First, look around. Notice anything out of place? It might be the first of several clues. Find all of them.
Got them? Now try to string them together. Work your way towards the answer, which in this case is two words. And how do you do that? That’s the challenge. Sorry for being cagey — I’ve already said too much!
If you solve the mystery — or even make partial progress — please let me know at firstname.lastname@example.org before midnight Eastern time on Wednesday, May 6. If you get stuck, there’ll be a hint announced in Bloomberg Opinion Today on Tuesday, May 5. Sign up here. (Apologies to those of you reading in syndication — to solve, you’ll need to look at the version of the column posted at bloomberg.com/opinion).
LAST WEEK’S CONUNDRUM
An eccentric warden was willing to set his 100 prisoners free if they could solve his light-switch puzzles.
Nicholas Glaeser, Jonathan Heckman, Felipe Rizzon, and many other astute readers* found a winning strategy on the warm-up version of the game. It involves 99 of the prisoners doing nothing more than turning the switch “on” the first time they see it “off.” The 100th prisoner is designated as the “counter.” This is an absolutely critical job, to say the least. The counter turns the switch “off” every time it is seen in the “on” position, and also records the number of flips he or she performs. The warden’s puzzle is solved once the switch is turned “off” 99 times.
We then moved on to the main event: a labyrinthine prison with 111 identical rooms, each with a number of switches in them — all of which, as before, start “off.” The goal: For some prisoner to determine when each of the hundred prisoners had been in every room at least 17 times.
The puzzle: How many switches do the prisoners need?
There are various ways to use some number of switches to label the rooms so the prisoners can tell them apart. Then, the prisoners can play the one-room strategy 17 times in each room to win their escape. As Jeremy Hurwitz and Leonardo Zapparoli figured out, the best version of that approach requires just three switches per room.
That’s a surprisingly small number — far lower than both the number of rooms and the number of times the prisoners have to visit each room.**
But believe it or not, it’s possible to win with even fewer: The prisoners actually only need two switches per room. The trick is that instead of counting one room at a time, they should count one prisoner at a time.***
How does that work? One prisoner is again the “counter.” At the start of the game, that prisoner turns both switches in some room “on.”
The other 99 prisoners all start “inactive.” Such a prisoner does nothing when he walks into a room unless he sees both switches “on.” In that case — if he hasn’t been “active” before — he becomes “active” and turns the second switch in that room “off.” Now he proceeds to turn the first switch “on” every opportunity he gets; once he’s done this 110 times, he knows he’s been in every room at least once, since all the switches started “off.” Then he turns all the first switches “off” again; after doing that 111 times, he knows he’s been in every room twice. He repeats the full cycle another eight times.
Once that’s done, all the rooms are back in the “off, off” starting state, and the prisoner knows he’s been in every room 17 times (in fact, 18 times).
Of course, that isn’t too useful unless he can somehow tell the “counter.” To do this, he sets one room’s switches in the only configuration that hasn’t been used yet: the first switch “off” and the second switch “on.” He then becomes inactive for the rest of the game.
When the “counter” sees a room in the “off, on” configuration, he or she learns that some prisoner has finished visiting all the rooms the requisite number of times. Then the “counter” turns both of the switches in that room “on,” and waits for a new prisoner to become active and complete his rounds.
Once the “counter” has seen the “off, on” configuration 99 times, he or she knows that all the other prisoners are done. Once the “counter” personally completes the series of nine toggling cycles through the rooms, it’s time to alert the warden to an incredible victory indeed!
Tynan Seltzer was the first to figure out the two-switch solution, followed (in order) by Bethany Burum and Alex Howlett, Jamie Balcombe and Alex Brett, Andrea Hawksley and Andrew Lutomirski, and Alex Newman-Smith.
(And if you’ve read this far, please don’t leave before you solve the hidden puzzle! It’s still lurking around somewhere.)
THE BONUS ROUND
Pay-it-forward puzzle books from Puzzazz (http://www.puzzazz.com/puzzles-with-heart) (hat tip: Roy Leban). Forgot your Uno deck at the office? You can turn a game of Magic: the Gathering into Uno with this 29-card combo (https://www.reddit.com/r/BadMtgCombos/comments/bpmc8g/turn_mtg_into_uno_with_one_simple_29card_trick/) (hat tip: Jay DeStories). Or test your mettle against a daily challenge from the card game SET (https://www.setgame.com/set/puzzle). Speculate on turnip futures in Nintendo’s Animal Crossing (https://www.ft.com/content/68f96d24-02f0-42fd-b132-aba0acba777f); take your Zoom calls to the enchanted world of Hayao Miyazaki (www.openculture.com/2020/04/hayao-miyazakis-studio-ghibli-releases-free-backgrounds-for-virtual-meetings.html); jam with a neural net jukebox (https://openai.com/blog/jukebox/); or just lay down some Seuss beats (https://www.youtube.com/watch?v=hqIbEHNqbPs&list=PLqvBBK0pPLrU9O6aGdGvD4ICXTGOH6FTa) (hat tip: Laura Messenheimer and Elizabeth Sibert). Build a Lego sculpture that supports itself through continuous tension (https://www.youtube.com/watch?v=6xbnrEqMr5Y&t=3m13s) or transform a steel bolt into a pocket safe (https://www.youtube.com/watch?v=KRgurx00G1o). And inquiring minds want to know: How did merchants in 19th-century Iran compute compound interest so quickly (https://twitter.com/docmilanfar/status/1254535220491022336)?
In addition to solutions, please send paradoxes, paraphernalia and/or your favorite puzzles to email@example.com.
*If you solved the puzzle and don’t see your name listed this week, 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.
**And notably, three switches suffice if we replace both 111 and 17 in the problem by other numbers.
***Daniel Kane and I have an in-progress paper in which we prove that two switches per room is the minimum possible. We also give a way to solve the problem one room at a time with only two switches, but it is really, really complicated.