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 next week’s column. If you need a hint or have a favorite puzzle collecting dust in your attic, find me on Twitter.
From Patrick Mayor comes a question about something we’re doing these days to keep ourselves and others safe: social distancing.
You’re walking along the middle of a wide sidewalk when you see someone walking toward you from the other direction, also down the middle of the sidewalk, 12 feet away. Being responsible citizens, you pass each other while maintaining a distance of at least 6 feet at all times. By the time you reach each other’s original positions, you should be back in the middle of the sidewalk again.
You should assume that the other person follows the same path you do, but flipped around (since they’re walking in the opposite direction). For example, you could both walk 3 feet to the left, 12 feet forward and finally 3 feet back to the right, walking a total of 18 feet before swapping positions.
Being lazy (I mean, efficient), you’d like to know the shortest distance you and the other person could walk so that you can switch positions, all while staying at least 6 feet apart at all times. What is this distance?
Extra credit: Now suppose the person walking toward you has no intention of straying from the center of the sidewalk (sigh), and it’s entirely up to you to maintain a distance of at least 6 feet. In this case, what is the shortest distance you would have to walk to reach the other person’s original position?
From Phil Imming comes his favorite riddle, which he was the only student in his calculus class to solve back in 1965:
One morning, it starts snowing. The snow falls at a constant rate, and it continues the rest of the day.
At noon, a snowplow begins to clear the road. The more snow there is on the ground, the slower the plow moves. In fact, the plow’s speed is inversely proportional to the depth of the snow — if you were to double the amount of snow on the ground, the plow would move half as fast.
In its first hour on the road, the plow travels 2 miles. In the second hour, the plow travels only 1 mile.
When did it start snowing?
Solution to last week’s Riddler Express
Congratulations to 👏 Chesson Yauk 👏 of Kansas City, Missouri, winner of last week’s Riddler Express.
Last week, you helped me get exactly 10 gloves out of a box. It was difficult to pull exactly two gloves out of the box at a time — sometimes I’d pull out two gloves, other times three and yet other times four. Somehow, I never pulled out any other number of gloves at a time.
How many distinct ways were there for me to remove all 10 gloves from the box? Note that the order mattered here — for example, pulling out two gloves, then four gloves and then another four gloves was distinct from pulling out four gloves, another four gloves and then two gloves.
One approach to this puzzle was to simply list out all the possibilities. Solver Andrew Heairet used a tree to work through each case:
Sure enough, there were 17 distinct ways to remove the gloves two, three or four at a time.
Many solvers, meanwhile, used a recursive approach. Suppose you already knew that there were f(N−4), f(N−3), f(N−2) and f(N−1) ways to remove N−4, N−3, N−2 and N−1 gloves, respectively. So then how many were there to remove N gloves? There were three distinct ways to reach N:
- There were f(N−4) ways to remove N−4 gloves, after which you could remove four gloves.
- There were f(N−3) ways to remove N−3 gloves, after which you could remove three gloves.
- There were f(N−2) ways to remove N−2 gloves, after which you could remove two gloves.
If you ever found yourself having removed N−1 gloves, however, then there was no way to remove N, since you couldn’t remove just one glove. That meant f(N), the number of ways to remove N gloves, was equal to f(N−4) + f(N−3) + f(N−2). Before applying this formula, you had to work out a few small cases: There was one way to remove zero gloves (you simply don’t remove any), zero ways to remove one glove, one way to remove two gloves and one way to remove three gloves.
From there, you could use the recursive formula to find that there were two ways to remove four gloves, two ways to remove five gloves, four ways to remove six gloves, five ways to remove seven gloves, eight ways to remove eight gloves, 11 ways to remove nine gloves and, sure enough, 17 ways to remove 10 gloves.
Finally, solver Benjamin Dickman used an advanced technique known as generating functions, looking at expressions like (x2 + x3 + x4)5. If you expand this expression, the coefficient of the x10 term winds up being the number of ways you can combine five twos, threes and fours to get a sum of 10. Similarly, the coefficient of the x10 term in (x2 + x3 + x4)4 tells you how many ways you can combine four twos, threes, and fours, and the coefficient of the x10 term in (x2 + x3 + x4)3 tells you how many ways you can combine three twos, threes, and fours. Combining these results, Benjamin once again found that there were 17 ways in total.
In the end, I was able to remove the gloves I needed — and I wasn’t stuck with one glove left over.
Solution to last week’s Riddler Classic
Congratulations to 👏 Kyle Tripp 👏 of Concord, CA, winner of last week’s Riddler Classic.
Last week, you started with a fair 6-sided die and rolled it six times, recording the results of each roll. You then wrote these numbers on the six faces of another, unlabeled fair die. For example, if your six rolls had been 3, 5, 3, 6, 1 and 2, then your second die wouldn’t have had a 4 on it; instead, it would have two 3s.
Next, you rolled this second die six times. You took those six numbers and wrote them on the faces of yet another fair die, and you continued this process of generating a new die from the previous one.
Eventually, you’d have a die with the same number on all six faces. What was the average number of rolls it would take to reach this state?
This puzzle got hairy quickly — after just one round, there were many possibilities to consider: You could still have all six numbers, or you could have five, four, three or two; there was even a small chance — 1 in 65, or 1 in 7,776 — that you’d roll the same number six times in a row and be done after just one round!
Many readers broke the problem down into cases. For example, if you knew the average number of rounds it would take when you had only two numbers left, you could work backwards to figure out how many rounds it would take when you had three numbers left. However, not all cases of having two numbers left were the same. While having one number on five faces (e.g., 1, 1, 1, 1, 1 and 2) gave you a whopping 33 percent chance of ending on the next round, having two numbers on three faces each (e.g., 1, 1, 1, 2, 2 and 2) provided a minuscule 3 percent chance of ending the next round. All that is to say — there were many cases to consider here.
Nevertheless, Riddler Nation powered through. Some turned to their computers, running countless simulations to arrive at an approximate answer. Angelos Tzelepis ran 2 million simulations, finding the average number of rounds was approximately 9.66.
Others were able to find an exact answer using Markov chains and transition matrices. Solver Allen Gu found that the average number of rounds was precisely 31,394,023/3,251,248, or about 9.656. (The original question asked for the number of rolls. Since each round had six rolls, I also accepted answers that were six times larger, or approximately 58.)
Last week’s extra credit went beyond 6-sided dice, asking you to consider N-sided dice. Again using Markov chains, Allen identified the average number of rounds up through 10-sided dice. Beyond that, things got … dicey. (Sorry.)
Angela Zhou went even further, demonstrating that the average number of rounds needed for an N-sided die was approximately 2N:
So if you had a fair 1,000-sided die, it would take a little under 2,000 rounds on average until all the faces were the same number.
If ever there was a time when you expected a linear relationship to appear in a Riddler Classic, this was not it.
Want more riddles?
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 firstname.lastname@example.org.