🚨🚨🚨 “The Riddler” book is out now! It’s chock-full of the best puzzles from this column (and, fret not, their answers) and some that have never been seen before. I hope you enjoy it, and thank you for riddling with us these past three years. 🚨🚨🚨
Welcome to The Riddler. Every week, I offer up problems related to the things we hold dear around here: math, logic and probability. There are two types: Riddler Express for those of you who want something bite-size and Riddler Classic for those of you in the slow-puzzle movement. Submit a correct answer for either,1 and you may get a shoutout in next week’s column. If you need a hint or have a favorite puzzle collecting dust in your attic, find me on Twitter.
Riddler Express
From Luke Robinson, a serenading stumper:
My daughter really likes to hear me sing “The Unbirthday Song” from “Alice in Wonderland” to her. She also likes to sing it to other people. Obviously, the odds of my being able to sing it to her on any random day2 are 364 in 365, because I cannot sing it on her birthday. The question is, though, how many random people would she expect to be able to sing it to on any given day before it became more likely than not that she would encounter someone whose birthday it is? In other words, what is the expected length of her singing streak?
Riddler Classic
From Moritz Hesse, some grazing geometry:
A farmer owns a circular field with radius R. If he ties up his goat to the fence that runs along the edge of the field, how long does the goat’s tether need to be so that the goat can graze on exactly half of the field, by area?
(The great thing about this puzzle, Moritz notes, is that if you get sick of math, you can find the answer through trial and error with your own circular field and your favorite goat, horse, cow, kangaroo, sheep, unicorn, centaur or sphinx.)
Solution to last week’s Riddler Express
Congratulations to 👏 Stefan Heidekrüger 👏 of Munich, winner of last week’s Riddler Express!
Last week’s Express brought a fill-in-the-blank challenge: What’s the next number in this series?
9, 10, 19, 24, 31, 40, 51, 64, 79, 90, ?
It’s A9.
A9?! What the … ?
The trick to filling in this blank was recognizing that these numbers aren’t in our usual base-10, or decimal, number system. Rather they are in the base-16, or hexadecimal, system. Hexadecimal is often used by computer programmers. And since we only have 10 digits that go with our usual base-10 system, base-16 uses the letters A through F to represent the values 10 through 15.
OK, back to our series. The pattern is \((N+2)^2\), where \(N\) is the number’s position in the sequence. So the first number is \(3^2\), or 9. The second number is \(4^2\), or 16, which is represented as 10 in hexadecimal. The third number is \(5^2\), or 25, which is 19 in hexadecimal. And so on. Our missing number is \(13^2\), or 169 — or A9 in hexadecimal.
Solution to last week’s Riddler Classic
Congratulations to 👏 Eric Roshan-Eisner 👏 of San Francisco, winner of last week’s Riddler Classic!
Last week you were brought in to solve a serious problem at the Riddler Intelligence Agency, or RIA. Namely, the RIA had been infiltrated by spies, and your job was to root them out. There were N agents total, and K of them were spies. You knew the values of N and K but not, at first, the identities of the spies. You could send any number of agents on a remote island retreat as many times as you wanted. If all of the spies were on the retreat, they would assemble for a secret spy meeting; if any of the spies were not on the retreat, the meeting would not take place. The only thing you learned from each retreat was whether or not this meeting happened.
It cost $1,000 per person to send agents on these retreats. What was the least you could spend while still identifying all of the spies? Assume you knew that N = 1,024 agents and K = 17 spies.
This week’s winner, Eric Roshan-Eisner, explained that it will take at least 122 retreats to identify all the spies: The total number of possible spy configurations within those 1,024 people is N choose K, or about \(4\cdot 10^{36}\). That number is very big — but it doesn’t mean we need that many retreats to suss out our spies.
Think of each retreat as a moment to learn one bit of information about the arrangement of spies (that is, whether or not the spy meeting occurred). I’m using “bit” there intentionally — the key to solving this puzzle is to translate that \(4\cdot 10^{36}\) number into binary, a number that needs 122 “bits” — one digit in a binary number — to be expressed. Every retreat you organize returns to you exactly one piece of yes-or-no, 0-or-1 information — that is, whether or not the spy meeting happened. That’s your bit. Therefore, the minimum number of retreats necessary to differentiate between all four undecillion possibilities is 122. The exact strategy you should use to do this, Eric wrote, is left as an exercise to the reader.
Others picked up the baton there. Tim Black, a grad student at the University of Chicago (Go Maroons!), found a strategy to identify the spies in 131 retreats, and also proved that it is impossible to do so in fewer than 122.
Thomas Swayze also found a 131-retreat strategy, which cost about $93 million. Thomas wrote that his strategy to find the spies was to use a form of binary search to single them out one by one: Start with some subset, S, of the agents that we know contains at least one spy. Then pick a subset, T, of S, and keep the agents in T at home while sending the entire rest of the agency on the retreat. If there’s a meeting, we know that T contains no spy — so leave all the agents in T out of all future retreats. If there is no meeting, there is some spy in T. Either way, we now have a smaller set that we know has a spy. Once we’ve outed one spy, we send him on all future retreats and repeat the process to find all the remaining spies, one by one. The tricky part is deciding how big to make the set T. It depends on the number of agents left, the number of spies we’ve caught, and the size of the set S. Thomas was kind enough to share the Python code he used.
Finally, Laurent Lessard described a strategy that used more retreats (191) but cost less (about $66 million).
But hey, if identifying spies were easy — or cheap — everybody would do it.
Want to submit a riddle?
Email me at oliver.roeder@fivethirtyeight.com.