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.
Quick announcement: Have you enjoyed the puzzles in this column? If so, I’m pleased to tell you that we’ve collected many of the best, along with some that have never been seen before, in a real live book! It’s called “The Riddler,” and it will be released in October — just in time for loads of great holidays. It’s a physical testament to the mathematical collaboration that you, Riddler Nation, have helped build here, which in my estimation is the best of its kind. So I hope you’ll check out the book, devour the puzzles anew, and keep adding to our nation by sharing the book with loved ones.
And now, to this week’s puzzles!
Riddler Express
From Daniel Jepson, put on your lab coat and step into Riddler Laboratories:
A centrifuge needs to be perfectly balanced along every axis before being run; otherwise, the torque will damage the internal rotor. If a centrifuge has N equally spaced buckets, some of which you’d like to fill with K samples, and all samples are of equal weight, for what values of K can all the samples be spun in the centrifuge safely?
Hint: You can run seven samples in a 12-bucket centrifuge. But you cannot run 10 samples in a 21-bucket centrifuge.
Riddler Classic
From Renaud Dubedout, a puzzle perfect for doodling during a boring class or meeting, not that I would ever endorse that sort of thing:
Start with an empty 5-by-5 grid of squares, and choose any square you want as your starting square. The rules for moving through the grid from there are strict:
- You may move exactly three cells horizontally or vertically, or you may move exactly two cells diagonally.
- You are not allowed to visit any cell you already visited.
- You are not allowed to step outside the grid.
You win if you are able to visit all 25 cells.
Is it possible to win? If so, how? If not, what are the largest and smallest numbers of squares you can legally visit?
Solution to last week’s Riddler Express
Congratulations to 👏 Al Shaheen 👏 of New Haven, Indiana, winner of last week’s Riddler Express!
Last week brought a numismatic puzzle: If Riddler Nation needed to make change (anywhere from 0.01 to 0.99) and was establishing its own mint, what values of coins would be ideal to yield the smallest number of coins in any transaction? When picking values, let’s say we’re limiting our mint to producing four coin denominations — replacing the current common American ones of penny, nickel, dime and quarter.
Picking one of the four Riddler Cash (℟) coins is easy: We know we’re going to need a 1¢ coin, because there’s no way to make ℟0.01 change without it. The other three coins we mint should have denominations of 5¢, 18¢ and 25¢.
The current system of penny, nickel, dime and quarter requires 4.7 coins to make change on average. A new system of penny, nickel, 18¢ and quarter denominations requires only 3.9 coins on average.
So it turns out that the current system isn’t too bad — we’d only need to change one denomination (stupid, tiny dimes) to achieve optimal change-making. The 18¢ piece makes certain values that were tough to create much easier. For example, to give 18¢ change under the current system, we’d need five coins — a dime, a nickel and three pennies. Now we need only one. Arriving at this solution, or any relatively efficient scheme, involves some guessing and checking, or computer programming. The key is to space your denominations so they efficiently account for all amounts between 0.01 and 0.99.
Solver Jochen Rick got to this result with a brute force program, and solver Tom Singer shared his write-up, wherein he employed a recursive algorithm. And, in fact, this problem has its own Wikipedia page, complete with code. Academic computer scientists have also tackled this problem, in one case in a paper titled “What This Country Needs is an 18¢ Piece.” Amen — that’ll solve everything.
Solution to last week’s Riddler Classic
Congratulations to 👏 Glenn Aaron Fisher 👏 of Bellingham, Washington, winner of last week’s Riddler Classic!
Last week found you at the helm of a ship in a precarious wartime situation. You were out to sea, wanting to get back safely to your home port. However, you spotted an enemy submarine sitting exactly halfway between you and the port. To sink you, the sub needed to be directly beneath your ship. The submarine submerged to some fixed depth, and you had no further information about its location or movement. The sub, however, could track your movement and respond efficiently. If you were fast enough, though, you could plot a wide course around the enemy and get home safely. How much faster than the sub did your ship need to be to ensure a safe arrival?
You need to be about 2.33 times faster.
This puzzle’s submitter, Mike Donner, explained why. Let’s say your ship must be at the very least k times faster than the submarine to get home safely. Since the submarine is halfway between you and the port, we know the ship needs to be more than two times faster — that is, k > 2. If that weren’t the case, the submarine could simply head straight toward your port and sink you there. We also know that if your ship is more than π times faster — that is, k > π — you could plot a full semicircular path around the sub’s starting location (making the distance between you and it the radius of the circle) and beat it home. So now we know the answer we seek — k — is somewhere between 2 and π.
But a straight line is not a wide enough route, and a semicircle is wider than it needs to be — we can be more efficient in our submarine-avoidance tactics.
Solver Thad Beier animated the situation you faced and the path you should take:
There are two sections to your efficient journey back to port, and they involve you baiting the submarine to come meet you before you speed past. The first is a beeline northwest, the second a curved course generally southwest. To solve for k, we need to put some math on top of this path.
Suppose the submarine starts at point (0, 0), your ship starts at point (1, 0), and your home port lies at point (-1, 0). The path we’re interested in examining happens when the ship plots a course around the sub such that given any angle, \(\theta\), the sub tries to intercept (starting after some angle \(\theta_i\)), the vessels arrive at the exact same time. Mike illustrated that like so:
So we have one polar curve ending at (-1, 0) and one straight line that meets it at \((x_i, y_i)\). Those two pieces also have the same slope at that point. Finally, the curved section of the path has the property that, as the angle \(\theta\) increases, the arc length increases k times as much as the radius, r, increases, like so:
This fact leads to a differential equation linking the variables named above:
\begin{equation*}ds = \sqrt{dr^2+(rd\theta)^2} = k dr\end{equation*}
This, in turn, leads to lots of painful calculus, trigonometry and algebra on our search for k. (My apologies, but hey, if navigating around an enemy sub were easy, everyone would do it.) You can find Mike’s full solution here. Additionally, you can find our winner Glenn’s work here and solver Sawyer Tabony’s tidy, tweet-sized solution here:
At the end of all of it, we find that k = 2.3325… Happy trails, sailor, and full steam ahead.
Want to submit a riddle?
Email me at oliver.roeder@fivethirtyeight.com.