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 Harry Smythe, an equine job interview question from his days working at an investment bank:
You, a very wealthy aristocrat, own 25 horses. You’re bored one day (you’re bored everyday) and decide to amuse yourself by identifying the three fastest horses in your stable. However, your personal racetrack is severely lacking in capacity, and you can only race five horses at a time. What is the minimum number of races you’ll need to organize to identify your three fastest horses?
Riddler Classic
From Jason Margiotta, a puzzle about spinning the big wheel:
On the brilliant and ageless game show “The Price Is Right,” there is an important segment called the Showcase Showdown. Three players step up, one at a time, to spin an enormous, sparkling wheel. The wheel has 20 segments at which it can stop, labeled from 5¢ up to $1, in increments of 5¢. Each player can spin the wheel either one or two times. The goal is for the sum of one’s spins to get closer to $1 than the other players, without going over. (Any sum over $1 loses. Ties are broken by a single spin of the wheel, where the highest number triumphs.)
For what amounts should the first spinner stop after just one spin, assuming the other two players will play optimally?
Solution to last week’s Riddler Express
Congratulations to 👏 Tom [last name withheld] 👏 of Los Angeles, winner of last week’s Express puzzle!
Last week you had to build a tower to please an oracle. You had four differently colored pieces that could be stacked in any order. But when you started building, you didn’t know what the correct order was. Upon assembling the pieces in some order, you could consult the architectural oracle who informed you if zero, one, two or all four pieces of the tower were in the correct position. Your tower wasn’t finished until the oracle confirmed your solution was correct. How many times did you have to consult the oracle, in the worst case, to assemble the tower correctly?
In the worst case, you’ll need five oracular consultations.
Many solvers submitted an answer of 24, arguing that the total number of possible tower arrangements — 4×3×2×1 — is also the number of consultations required. But that isn’t quite right. You won’t need to ask the oracle about every possible order, even in the worst-case scenario, because you learn a lot about the makeup of the correct tower as you go.
Our winner, Tom, walks us through one such worst case:
Think of the blocks as lettered and start by stacking them ABCD.
- The oracle says “zero.” Swap A and B: Ask about BACD.
- The oracle says “zero.” Therefore, neither A nor B can be in the first or second position. Swap B and A for C and D: Ask about CDBA.
- The oracle says “two.” Swap C and D: Ask about DCBA.
- The oracle says “zero.” Swap C and D for B and A: Ask about CDAB. (You know this is correct but must consult the oracle to confirm, per the rules.)
- The oracle says “four,” and you’re done!
Thad Beier illustrated all the ways your construction and consultation could unfold. Each number on the tree represents an answer Frank, the oracle, might give. Each step down the tree is an extra guess it may take if you get your first guess wrong.
Solution to last week’s Riddler Classic
Congratulations to 👏 Ethan Rubin 👏 of Newcastle, California, winner of last week’s Classic puzzle!
Last week you were presented with this carceral situation: One hundred prisoners are put into 100 completely isolated cells, numbered 1 to 100. Once they are in their cells, they cannot communicate with each other in any way. They are taken by the warden one at a time, but in no particular order, to a special room, Cell 0, in which there are two levers. As the prisoners enter the room, each lever is either up or down, but the levers’ starting positions are unknown. When in the room, a prisoner must flip exactly one of the levers. At any point, any prisoner may declare to the warden that all of the prisoners have been to the room. (The warden will take prisoners to the room indefinitely until someone makes a guess.) If the prisoner is correct, they are all released. If not, they are all executed. What strategy can the prisoners devise beforehand that will guarantee their release? How many trips to Cell 0 will it take on average before they are released?
To guarantee their freedom, the prisoners can establish a division of labor. First, they designate one among them as the Counter. The rest are merely drones. Second, they designate one of the levers the “count lever” and one of the levers the “dummy lever.” The rest of the details are adapted from the explanation of this week’s winner, Ethan:
The Counter’s job is simple — he adds one to his running total every time he enters Cell 0 and finds the count lever up, and when he does, he flips the count lever back down. If he sees the count lever down, he leaves it alone and flips the dummy lever. The drones do the opposite. If they enter Cell 0 and see the count lever down, they flip it up. If they see it up, they leave it alone and flip the dummy lever instead. Every drone should flip the count lever only twice during their entire stay in the prison. The Counter should declare to the warden that everyone has entered the room — and guarantee their freedom — once his tally hits 199.
Why 199 and not 99? And why do the drones need to flip the count lever twice? Because the prisoners don’t know the initial positions of the levers, there is a small chance that the Counter is chosen to enter Cell 0 first and enters to finds the count lever up. (This is only a 1-in-200 chance, but 100 lives are on the line!) In that case, he wouldn’t know for sure whether to add a legitimate tally to his total or not. So by counting through the prisoners twice, the Counter can be 100 percent sure they’ve all been to the room and avoid any chance of execution. Once the tally reaches 199, the Counter can be certain that 99 of the prisoners have entered Cell 0 at least twice and all 100 prisoners have entered it at least once.
This process will take roughly 20,000 total prisoner trips to the room, on average. You can arrive at a rough approximation of this total by observing that the Counter enters the room about once every 100 trips, and he needs to tally 199 up levers, for a total of 19,900. (But this ignores those occasions where the Counter enters the room twice finding the count lever unflipped.) A more precise answer can be found using the negative binomial distribution, which gives about 20,500 trips on average. Much more detail on problems like this can be found in this paper by Yisong Song.
Solver Curt Nehrkorn simulated the probability distribution of the number of trips it might take until freedom:
If each visit takes one minute and the warden drags the prisoners to Cell 0 around the clock, the prisoners should be free in about two weeks. Well worth the wait.
Want to submit a riddle?
Email me at oliver.roeder@fivethirtyeight.com.