It’s Elementary, My Dear Riddler!
Illustration by Guillaume Kurkdjian
Welcome to The Riddler. Every week, I offer up problems related to the things we hold dear around here: math, logic and probability. Two puzzles are presented each week: the Riddler Express for those of you who want something bite-size and the 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 the next column. Please wait until Monday to publicly share your answers! If you need a hint or have a favorite puzzle collecting dust in your attic, find me on Twitter.
Riddler Express
From Eric Snyder comes a not-so-final problem:
Dr. Watson and Sherlock Holmes are tracking a criminal mastermind in the present-day United States. Watson lists out the states the mastermind has visited in alphabetical order. They are: Alabama, Arkansas, California, Colorado, Florida, Georgia, Indiana, Louisiana, Maryland, Minnesota, Missouri, Montana, Nebraska, New Hampshire, North Dakota, Pennsylvania and South Carolina.
Watson stares at the list, but he can’t make out any sort of pattern.
But Holmes’s eyes light up. “Why, it’s elementary, my dear Watson!”
What pattern did Holmes notice?
The solution to this Riddler Express can be found in the following column.
Riddler Classic
From Ross O’Brien comes a game of nonconformist dice:
You have four fair tetrahedral dice whose four sides are numbered 1 through 4.
You play a game in which you roll them all and divide them into two groups: those whose values are unique, and those which are duplicates. For example, if you roll a 1, 2, 2 and 4, then the 1 and 4 will go into the “unique” group, while the 2s will go into the “duplicate” group.
Next, you reroll all the dice in the duplicate pool and sort all the dice again. Continuing the previous example, that would mean you reroll the 2s. If the result happens to be 1 and 3, then the “unique” group will now consist of 3 and 4, while the “duplicate” group will have two 1s.
You continue rerolling the duplicate pool and sorting all the dice until all the dice are members of the same group. If all four dice are in the “unique” group, you win. If all four are in the “duplicate” group, you lose.
What is your probability of winning the game?
The solution to this Riddler Classic can be found in the following column.
Solution to last week’s Riddler Express
Congratulations to 👏 Mike Strong 👏 of Mechanicsburg, Pennsylvania, winner of last week’s Riddler Express.
Last week, you were on the 10th floor of a tower and wanted to exit on the first floor. You got into the elevator and hit 1. However, this elevator was malfunctioning in a specific way. When you hit 1, it correctly registered the request to descend, but it randomly selected some floor below your current floor (including the first floor). The car then stopped at that floor. If it wasn’t the first floor, you again hit 1 and the process repeated.
Assuming you were the only passenger on the elevator, how many floors on average did it stop at (including your final stop, the first floor) until you exited?
Suppose the average number of stops from floor i was Ei. You immediately knew that E1 was 0, since there were no further stops after the first floor. You also knew that E2 was 1, because once you were on the second floor, you were guaranteed to reach the first floor on your very next stop.
Things got a little more complicated on higher floors. Suppose you were on the Nth floor. From there, you had a 1/(N−1) probability of stopping on each of the lower floors. And from each of those floors, you had a corresponding average number of stops remaining. Many solvers, including Adnan Haque, realized this meant you could write an equation for EN:
EN = (E1 + E2 + E3 + … + EN−1)/(N−1) + 1
The 1 that was added at the end came from the fact that the button press on the Nth floor accounted for one stop. Multiplying both sides of this equation by N−1 gave you:
(N−1)·EN = E1 + E2 + E3 + … + EN−1 + N−1
A key insight was that you could also derive a similar equation for EN+1:
N·EN+1 = E1 + E2 + E3 + … + EN−1 + EN + N
Substituting one of those equations into the other helped you eliminate all those pesky averages from the lower floors, leaving you with:
N·EN+1 = (N−1)·EN + EN + 1
And rearranging this equation left you with the much simpler recurrence relation:
EN+1 = EN + 1/N
Solver Oscar Lanzi III arrived at this same equation in a slightly different way. From the (N+1)th floor, you had a 1/N chance of next stopping on the Nth floor, and a (N−1)/N chance of going to any other floor — which was collectively equivalent to starting at the Nth floor. As an equation, this meant:
EN+1 = 1/N·(EN + 1) + (N−1)/N·EN
Sure enough, this simplified to the exact same recurrence relation.
But regardless of how you derived it, because E2 was 1, that meant E3 was 1 + 1/2. And E4 was 1 + 1/2 + 1/3. This pattern continued all the way up to E10 — the average number of stops when you started from the 10th floor — which was 1 + 1/2 + 1/3 + 1/4 + 1/5 + 1/6 + 1/7 + 1/8 + 1/9, or about 2.829 stops.
This harmonic series has appeared in The Riddler before, and I’m sure it will again. In the meantime, consider packing a sandwich for any randomly long elevator rides.
Solution to last week’s Riddler Classic
Congratulations to 👏 Glenn Horton-Smith 👏 of Manhattan, Kansas, winner of last week’s Riddler Classic.
As you may know, a word ladder is a sequence of words in which exactly one letter changes from one word to the next. And an optimal word ladder gets you from the initial word to the final word using as few other words as possible. For example, to go from DOG to CAT, an optimal word ladder has just four total words (including DOG and CAT): DOG, DOT, COT and CAT.
Last week, you had to find optimal prime ladders. Every number in the ladder had to be prime, with exactly one digit changing from one number to the next. For example, here is an optimal prime ladder that goes from 97 to 53 with just four total numbers: 97, 17, 13 and 53.
This is tied for the longest optimal prime ladder consisting of two-digit primes.
What was the longest optimal prime ladder for three-digit primes? Four-digit primes? Five-digit primes?
While this may have sounded like an exercise in number theory, solvers like Jenny Mitchell noted that it was actually a problem rooted in graph theory. If you considered the different prime numbers to be nodes, then two prime nodes were connected by an edge whenever they differed by exactly one digit. That enabled you to construct a graph for three-digit primes, another graph for four-digit primes and a third graph for five-digit primes. Solver Joao Coelho illustrated the graph for three-digit primes:
From there, finding the longest optimal prime ladder was equivalent to determining the diameter of this graph — that is, the two connected nodes that are farthest apart.
Finding the diameters of graphs with hundreds or thousands of nodes is very difficult to do by hand, so solvers turned to computers and some time-tested algorithms for help. For three-digit primes, the longest optimal prime ladder consisted of seven numbers (example: 389, 379, 179, 109, 101, 701 and 761). For four-digit primes, the longest ladder had nine numbers (example: 2,441, 5,441, 5,449, 5,849, 5,869, 6,869, 6,899, 6,199 and 9,199). And for five-digit primes, the longest ladder had 11 numbers (example: 88,259, 78,259, 76,259, 96,259, 96,269, 96,469, 96,461, 96,661, 99,661, 99,761 and 99,721).
For extra credit, you had to find the longest optimal prime ladder for six-digit primes, and that’s where the puzzle took an unusual turn. For two-digit primes, three-digit primes, four-digit primes and even five-digit primes, the resulting graphs were connected, meaning it was possible to generate a ladder from every prime to every other prime. But that was not the case for six-digit primes. Solver Laurent Lessard noted that among the 68,906 six-digit primes, six primes — 294,001, 505,447, 584,141, 604,171, 929,573 and 971,767 — were not connected to the other 68,900 (which were themselves all connected). Among the remaining primes, the longest optimal ladder had 13 numbers (example: 440,497, 410,497, 410,491, 710,491, 710,441, 710,443, 717,443, 917,443, 917,843, 907,843, 905,843, 905,833 and 995,833).
By the way, since submitting this puzzle to me, Michael Branicky has published the sequence of optimal ladder lengths on the On-Line Encyclopedia of Integer Sequences. Riddler Nation strikes OEIS again!
Want more puzzles?
Well, aren’t you lucky? There’s a whole book full of the best puzzles from this column and some never-before-seen head-scratchers. It’s called “The Riddler,” and it’s in stores now!
Want to submit a riddle?
Email Zach Wissner-Gross at riddlercolumn@gmail.com.
