Can You Catch The Grasshopper?
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.
Based on a conversation from satyreyes comes a puzzle for which you might seek some medical attention:
Every day on a certain ward at Riddler Hospital, one patient is admitted who needs one day of treatment, one who needs two days and so on, up to seven days. Each patient remains in their own room for the duration of their stay.
You are a nurse who is assigned to a room at random on a particular day. What is the probability that the patient you see in that room will still be there tomorrow?
The solution to this Riddler Express can be found in the following column.
You are trying to catch a grasshopper on a balance beam that is 1 meter long. Every time you try to catch it, it jumps to a random point along the interval between 20 centimeters left of its current position and 20 centimeters right of its current position.
If the grasshopper is within 20 centimeters of one of the edges, it will not jump off the edge. For example, if it is 10 centimeters from the left edge of the beam, then it will randomly jump to anywhere within 30 centimeters of that edge with equal probability (meaning it will be twice as likely to jump right as it is to jump left).
After many, many failed attempts to catch the grasshopper, where is it most likely to be on the beam? Where is it least likely? And what is the ratio between these respective probabilities?
The solution to this Riddler Classic can be found in the following column.
Solution to last week’s Riddler Express
Congratulations to 👏 Liam 👏 of Los Angeles, California, winner of last week’s Riddler Express.
Last week, you saw how you could add or multiply the counting numbers 1, 2 and 3 — using each number at most once, and in any order — to make all the numbers from 1 to 9:
However, there was no way to make the number 10. Therefore, 10 was the First Unmakeable Number, or “FUN,” for the first three counting numbers.
What was the FUN for the first four counting numbers?
As we already said, numbers 1 through 9 could already be generated just using 1, 2 and 3. Starting at 10, you could continue generating numbers all the way up to 21. Many solvers, like Mary Lo, were kind enough to show how they generated each number. Here was how Mary generated the different numbers:
However, there was no way to generate 22, which meant it was indeed the FUN for the first four counting numbers. The Hewitt School Math Teachers demonstrated this by noting that the only way to make 22 would be to do one of the following: make 11 using 1, 3 and 4 (not possible) and then multiplying by 2; making 18 using 1, 2 and 3 (not possible) and then adding 4; making 19 using 1, 2 and 4 (not possible) and then adding 3; making 20 using 1, 3 and 4 (not possible) and then adding 2; and making 21 using 2, 3 and 4 and then adding 1. In short, it wasn’t possible.
For extra credit, you were asked to find as many “FUNs” as you could.
As I had expected, a number of solvers wrote computer code to do this for them. A straightforward algorithm was an exhaustive one — trying every possible arrangement of numbers, operations and orders — and then identifying the smallest number that couldn’t be generated.
If we denote the FUN of the first N counting numbers as FUN(N), then we know that FUN(3) = 10 and FUN(4) = 22. The puzzle’s submitter, Dean Ballard, had further found that FUN(5) = 58, FUN(6) = 233, FUN(7) = 827 and FUN(8) = 3359 and FUN(9) = 16,631. Solver Michael Branicky extended Dean’s sequence, further finding that FUN(10) = 114,371, FUN(11) = 708,278, FUN(12) = 3,975,838 and FUN(13) = 35,724,478. To my knowledge, FUN(14) and beyond remain unknown.
A few readers also extended the puzzle in other ways, such as including additional operations like subtraction and division. I wanted to highlight one such extension, courtesy of Nahiphog over Twitter: Using the operations of addition, subtraction, multiplication and division, which four counting numbers could you have used to produce the greatest possible FUN? According to Nahiphog, using the numbers 2, 3, 14 and 60, you could have generated every number up to and including 86, meaning the FUN was 87:
Now if that’s not FUN, I don’t know what is.
Solution to last week’s Riddler Classic
Congratulations to 👏Sam Dittmer 👏 of Playa Vista, California, winner of last week’s Riddler Classic.
Last week, you were stranded in the Great Riddlerian Desert, where there was a single oasis that was straight and narrow. There were N travelers who were trapped at the oasis, and one day, they agreed that they would all leave. They independently picked a random location in the oasis from which to start and a random direction in which to travel. Once their supplies were packed, they all headed out.
What was the probability that none of their paths would have intersected, in terms of N? (For the purposes of this puzzle, you were asked to assume that the oasis was a line segment, while the desert was an infinite Cartesian plane.)
Suppose (“without loss of generality,” as mathematicians might say) that the oasis ran east-west. Then, some subset of travelers departed in a northerly direction while the others departed in a southerly direction. The graphic below shows an example N was 7, with three travelers headed north and four headed south:
For this particular example, none of the travelers’ paths intersected. Why was that? Well, looking at the three northern travelers, it was because if you considered them from west to east, their directions kept rotating clockwise. And if you looked at the four southern travelers from west to east, their directions rotated counterclockwise.
If three northern travelers went in three random northerly directions, of the 3! (or six) ways to order them from left to right, only one would have resulted in a west-to-east clockwise rotation, and therefore no intersections. So the probability of this occurring was 1/6.
Now, to solve the original problem, you had to consider N travelers. Each traveler was equally likely to head north versus south, so the probability of having k northern travelers was N choose k multiplied by (1/2)N. In factorial notation, this was N!/(k!(N−k)!)·(1/2)N. You then had to multiply that by the probability that the northern travelers were all properly arranged, 1/k!, as well as the probability that the southern travelers were all properly arranged, 1/(N−k)!. Finally, you had to add up the probabilities for the exclusive cases where k was anywhere from 0 to N. In other words, it was the sum where k went from 0 to N of N!/(k!(N−k)!)2·(1/2)N.
Many solvers left their answers in this form. However, there were ways to simplify it, or at least write it without using a summation. Multiplying the numerator and denominator inside the summation by a factor of N! and then pulling out a factor of 1/2N·(1/N!) left you with (N choose k)2 inside the summation. The resulting summation happens to be equivalent to 2N choose N, or (2N)!/(N!)2. After all that work, the summation was gone, and the probability of no intersections was (2N)!/(2N·(N!)3).
As N increased, this probability got really small really fast. Solver Laurent Lessard applied Stirling’s approximation to show that, for large N, the probability of no intersections was proportional to (2e/N)N+1, a result that agreed nicely with an approximation argument form solver Josh Silverman.
Whether their paths crossed or not, I have it on good authority that all N travelers made it safely out of the Great Riddlerian Desert.
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 firstname.lastname@example.org.