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 Max Weinreich, a lost digit begging to be found:
I multiplied together some of the integers from 1 to 99. I got a big number in return:
530,131,801,762,787,739,802,889,792,754,109,70_,139,358,547,710,066,257,652,050,346,294,484,433,323,974,747,960,297,803,292,989,236,183,040,000,000,000.
What’s the missing digit?
Riddler Classic
From Jerry Meyers, you’re going to have to science the shit out of this:
Congratulations, astronaut! You’ve been selected for the first manned mission to Mars. You are slated to spend five Earth-years on the surface of the red planet (1,825 Earth-days — you can ignore leap years).
Conditions on the planet will be brutal, and they will be especially rough on the equipment required to keep you alive. In fact, it is known that exactly one vital piece of equipment will break each day. Therefore, you and the rest of the international team of astronauts will be sent with three 3D printers to print replacement parts for critical equipment.
Each printer is manufactured in a different country, however, and therefore parts from one printer are not compatible with any of the other printers (that means no scavenging allowed). If something breaks on a 3D printer, you will have to use one of the other 3D printers to print a replacement part. Any part can be printed effectively instantly, though any given printer only has the power to print one piece a day.
The Riddler Aeronautics and Space Administration (RASA) has tested all three printers and found that, in addition to the daily breakage of the vital life-support equipment, one has a 10 percent chance of something breaking on any given day, the second a 7.5 percent chance and the last a 5 percent chance. If you can’t quickly print a replacement part for any piece of vital equipment, you’ll die.
What are the chances that you make it home alive?
Solution to the previous Riddler Express
Congratulations to 👏 Nick McGowan-Lowe 👏 of Dunblane, Scotland, winner of the previous Riddler Express!
Last week, a bookworm crawled into your Christmas present: a 20-volume encyclopedia. You had those volumes arranged in numerical order on your shelf, and the bookworm ate from the first page of the first volume to the last page of the last volume. Each volume was 2 centimeters thick and bound with a 2-millimeter-thick hardcover. How far did the bookworm eat?
It ate through 36.4 centimeters.
OK, OK, this was sort of a trick question. The “trick” is that the first page of the first volume, when the volumes are arranged on your shelf, is on the right-hand side of the volume — the bookworm barely ate through any of that volume. And the last page of the last volume, similarly, is on the left-hand side — the bookworm ate through hardly any of that volume, too.
So the bookworm ate through 18 entire volumes plus two extra hardcovers (one from the first volume and one from the last). That’s 18*(2cm) + 2*(2mm), or 36.4 centimeters.
Solution to the previous Riddler Classic
Congratulations to 👏 Ravi Fernando 👏 of Berkeley, California, winner of the previous Riddler Classic!
Last week’s puzzle came in the form of an image that hid some lovely mathematical ideas. Specifically, you were asked: What are the bits below?
The key to breaking down this monolith is to look for patterns — regularities in the bits that might suggest an encompassing logic to the noisy-looking color. But there are a few ways to arrive at a solution. This puzzle’s submitter — Jordan Ellenberg, a math professor at the University of Wisconsin — has the solution(s) for us this week:
We can think of the picture as a function that takes a pair of numbers (m,n) and returns either 0 or 1. (In this case, blue is 0 and red is 1.) So, for starters, looking at the bottom row and leftmost column, we see that f(m,0) = f(0,m) = 0 for any number m. And, as many people observed, the diagram is symmetric around its main diagonal line, m = n, so we also know that f(m,n) = f(n,m).
But that’s not the only regularity we could find. The second row, for example, alternates between red and blue. We can write that fact as f(1,n) = 1 + f(1,n-1), where our convention is to work modulo 2, so that 1+1 = 0. So f(1,0) = 0, f(1,1) = 1, f(1,2) = 0, f(1,3) = 1, and so forth.
What about the next row? This one is periodic too, if you look closely. The pattern is blue, blue, red, red, blue, blue, red, red, etc. Also, the color of a square in Row 2 is always the opposite color from the square two blocks to its left; in other words, f(2,n) = 1 + f(2,n-2), whenever n is at least 2.
Now this suggests a pattern! Does the next row obey the rule f(3,n) = 1 + f(3,n-3)? If so, the colors would have to repeat every six blocks. And they do! The colors are blue, red, red, red, blue, blue, blue, red, red, red, etc., and the pattern holds. You can check it as far up as you like. Whenever the second coordinate is at least as big as the first, we have f(m,n) = 1 + f(m,n-m).
OK, so we’ve found two regularities in the pattern. But now comes something wonderful. These two rules, together with the stipulation that f(n,0) = 0, determine all the bits! Let’s see how this works. Suppose we want to compute f(14,38). We have
f(14,38) =
1 + f(14,24) =
2 + f(14,10) =
2 + f(10,14) =
3 + f(10,4) =
3 + f(4,10) =
4 + f(4,6) =
5 + f(4,2) =
5 + f(2,4) =
6 + f(2,2) =
7 + f(2,0) = 7 + 0 = 7
And since 7 is odd and we’re working in modulo 2, we have a red square in position (14,38). (In this case, 7 mod 2 equals 1, which is red.)
Given our two rules and their accompanying functions, no matter where you start, you can always either subtract the first number from the second or flip the two numbers so the second one is bigger; the process stops when one coordinate becomes zero, at which point you know the value of f. This is an answer to the riddle, if you want! The bits are the values of the function f determined recursively by those two rules.
But it’s not my answer — I have something else in mind that builds on the solution we just found. That procedure we just went through with 14 and 38? I didn’t invent it. It’s been around for more than 2,000 years. It’s Euclid’s algorithm for computing the greatest common divisor of two whole numbers, one of the very first formal algorithms ever written down. It turns out that the greatest common divisor of m and n is always the value one coordinate has when the other coordinate crashes out at zero. In the example above, we’ve computed that the greatest common divisor of 14 and 38 is 2.
So here’s another right answer: the box at (m,n) is blue if the number of subtraction steps in the Euclidean algorithm, starting with (m,n), is even; it is red if that number of steps is odd.
But that’s not my answer either. My real answer involves fractions. Remember the 38 and 14 before? Suppose they were given to you as a fraction (38/14), rather than coordinates in a function. Remember how your middle-school math teacher didn’t like improper fractions? They wanted you to write it as a “mixed number”: 2 10/14. So far, so good. But what about that 10/14? Let’s write that as a mixed number, too. 10/14 = 1 / (14/10) = 1 / (1 + 4/10). Putting it all together, we get 38/14 = 2 + 1 / (1 + 4/10).
Why stop there! 4/10 is 1/(10/4) and 10/4 is 2 2/4. Keep going and we end up with 38/14 = 2 + 1/ (1 + 1/ (2 + 1/2)). You can do this with any fraction. To make this a little easier to read, we can dispense with all the “one overs” and simply write 38/14 = [2,1,2,2]. This is called the continued fraction expansion of 38/14 (or, equivalently, of 19/7). You can write any fraction this way. In fact, you can write any real number this way, but if the number is irrational, the continued fraction expansion never stops! For instance, the continued fraction of π is [3,7,15,1,292,1,1,1 …]. A continued fraction is sort of like a decimal expansion, only much, much better. Just like a decimal, you can cut it off at any point and get an approximation of the irrational number under discussion, but the continued fraction is much better at finding simple approximations that are really good. Like [3,7] = 3 + 1/7 = 22/7, an approximation of π that was known to Archimedes. Or the even better [3,7,15,1] = 355/113, an incredibly close rational approximation of π discovered by Zu Chongzhi in the 5th Century.
So what does all this have to do with the red and blue squares? Well, look back to our computation for 38/14. When we write it as the mixed fraction 2 10/14, we’re saying you can subtract 14 from 38 twice before you get something less than 14. In other words, the Euclidean algorithm has two subtraction steps before you have a flip step — one of our two “rules.” Look back at our Euclidean algorithm calculation and you see that it goes: subtract, subtract, flip, subtract, flip, subtract, subtract, flip, subtract, subtract. The continued fraction coefficients [2,1,2,2] are just the number of subtractions in between the flips. And the total number of subtractions is precisely the sum of the continued fraction coefficients.
And that was what I was computing when I made that picture: In box (a,b) I recorded whether the sum of the continued fraction coefficients of b/a was even or odd.
There are any number of fun variants. You can look at the sum of the continued fraction coefficients modulo 3 instead of modulo 2, plotting the three options in three different colors:
Or instead of 3, you could work modulo 5.
Both of these plots present the eye with a rather beautiful appearance of structure. You see a kind of rectilinear scoring in the mod 3 picture and ovoid regions mod 5. I have no explanation for these apparent structures.
Do you?
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 me at oliver.roeder@fivethirtyeight.com.