Can You Hop to the Lily Pad?

You’re a frog whose lifelong dream has been to make it to lily pad number 1. Do you have what it takes to realize this dream, or will random hopping lead you astray?

Welcome to Fiddler on the Proof! The Fiddler is the spiritual successor to FiveThirtyEight’s The Riddler column, which ran for eight years under the stewardship of myself and Ollie Roeder.

Each week, I present mathematical puzzles intended to both challenge and delight you. Beyond these, I also hope to share occasional writings about the broader mathematical and puzzle communities.

Puzzles come out Friday mornings (8 a.m. Eastern time). Most can be solved with careful thought, pencil and paper, and the aid of a calculator. Many include “extra credit,” where the analysis gets particularly hairy or where you might turn to a computer for assistance.

I’ll also give a shoutout to 🎻 one lucky winner 🎻 of the previous week’s puzzle, chosen randomly from among those who submit their solution before 11:59 p.m. the Monday after that puzzle was released. I’ll do my best to read through all the submissions and give additional shoutouts to creative approaches or awesome visualizations, the latter of which could receive 🎬 Best Picture Awards 🎬.

This Week’s Fiddler

From Michael Coffey comes a hoppin’ good puzzle:

You are a frog in a pond with four lily pads, marked “1” through “4.” You are currently on pad 2, and your goal is to make it to pad 1. From any given pad, there are specific probabilities that you’ll jump to another pad:

• Once on pad 1, you will happily stay there forever.

• From pad 2, there’s a 1-in-2 chance you’ll hop to pad 1, and a 1-in-2 chance you’ll hop to pad 3.

• From pad 3, there’s a 1-in-3 chance you’ll hop to pad 2, and a 2-in-3 chance you’ll hop to pad 4.

• Once on pad 4, you will unhappily stay there forever.

Given that you are starting on pad 2, what is the probability that you will ultimately make it to pad 1 (as opposed to pad 4)?

This Week’s Extra Credit

From Michael Coffey also comes some Extra Credit:

Once again, you are a frog in a pond. But this time, the pond has infinitely many lily pads, which are numbered “1,” “2,” “3,” etc. As before, you are currently on pad 2, and your goal is to make it to pad 1, which you would happily stay on forever.

Whenever you are on pad k, you will hop to pad k−1 with probability 1/k, and you will hop to pad k+1 with probability (k−1)/k.

Now, what is the probability that you will ultimately make it to pad 1?

Making the ⌊Rounds⌉

There’s so much more puzzling goodness out there, I’d be remiss if I didn’t share some of it here. This week, I’m sharing a question from science fiction author Greg Egan:

Pick N points on a sphere, equally spaced on the circle at an angle 𝜃 from the pole.

Rotate the sphere around each of the points in turn by the same angle, 𝛼.

What value should 𝛼 be, in order for the net rotation to restore the sphere to its original orientation?

The link comes with an animation showing a successful sequence of rotations for N = 3 and 𝜃 = 30 degrees.

Feel free to discuss this puzzle and your approach in the comments below.

Want to Submit a Puzzle Idea?

Then do it! Your puzzle could be the highlight of everyone’s weekend. If you have a puzzle idea, shoot me an email. I love it when ideas also come with solutions, but that’s not a requirement.

Standings

I’m tracking submissions from paid subscribers and compiling a leaderboard, which I’ll reset every quarter. All timely correct solutions to Fiddlers and Extra Credits are worth 1 point each. At the end of each quarter, I’ll 👑 crown 👑 the finest of Fiddlers. (If you think you see a mistake in the standings, kindly let me know.)

Last Week’s Fiddler

Congratulations to the (randomly selected) winner from last week: 🎻 Dinant Krijgsman 🎻 from Borne, Netherlands. I received 63 timely submissions, of which 56 were correct—good for an 89 percent solve rate.

Last week, you analyzed a bean machine like the one shown below. The topmost row had three pins (and two slots for a ball to pass through), while the bottommost row had two pins (and three slots for a ball to pass through). The remaining rows alternated between having three pins and two pins.

But instead of the 12 rows of pins in the illustrative diagram, the board had many, many rows. And at the very bottom of the board, just below the two bottommost pins, were three buckets, labeled A, B, and C from left to right.

Whenever a ball encountered one of the leftmost pins, it traveled down the right side of it to the next row. And whenever a ball encountered one of the rightmost pins, it traveled down the left side of it to the next row.

But this wasn’t your garden variety bean machine. Whenever a ball encountered any of the other pins, it had a 75 percent chance of traveling down the right side of that pin, and a 25 percent chance of traveling down the left side of that pin.

A single ball was about to be dropped into the left slot at the top of the board. What was the probability that the ball ultimately landed in bucket A, the leftmost slot at the bottom?

One approach was to figure out the probability distributions one row at a time. You were told that the ball passed through the left slot in the first row. For the second row, the probability of going through the leftmost slot was 1/4, the middle slot was 3/4, and the rightmost slot was 0. For the third row, the probability of going through the left slot was 1/4 + (1/4)·(3/4). The first term accounted for the ball coming down from the left, and the second term accounted for the ball coming down from the right. This sum came to 7/16, which meant the probability the ball passed through the right slot in the third row was 1−7/16, or 9/16.

If you kept calculating these probabilities row by row, you wound up with a table of values that looked like the following, courtesy of solver John:

The probabilities definitely seemed to be converging to specific values. Now, the puzzle was asking for the probability that the ball passed through the leftmost slot in a row with three slots. Based on the diagram, this value appeared to converge to something between 2 and 3 percent.

To determine the exact value, solvers like Ryan Lafitte looked at a more general probability distribution, in which the probability the ball passed through the left slot of a given row with two slots was p, which meant the probability it passed through the right slot was 1−p.

What were the probabilities for the next row, which had three slots?

• The probability for passing through the leftmost slot was p/4.

• The probability for passing through the middle slot was 3/4·p + 1/4·(1−p), or p/2 + 1/4.

• The probability for passing through the rightmost slot was 3/4·(1−p), or 3/4 − 3/4·p.

Sure enough, these three probabilities summed to 1 (they had to—but it’s always a nice confirmation of one’s algebra when everything checks out).

Next, you could take this one more step, using these three probabilities to compute the distribution for the next row, which again had two slots:

• The probability for passing through the left slot was p/4 + 1/4·(p/2 + 1/4), or 3/8·p + 1/16.

• The probability for passing through the right slot was 3/4·(p/2 + 1/4) + 3/4 − 3/4·p, or 15/16 − 3/8·p.

As expected (and required), these two probabilities summed to 1.

Okay, now here’s the best part: After many, many rows of the bean machine, and as suggested by the convergent behavior we saw above, we could expect the probabilities to approach some steady state, meaning they didn’t change from one pair of rows to the next. In other words, the probability distribution for one row with two slots, which we said was p and 1−p, was exactly the same as the distribution for the next row with two slots, which we found was 3/8·p + 1/16 and 15/16 − 3/8·p.

Making these distributions equal required that the probabilities for passing through the left slot were equal: p = 3/8·p + 1/16. Solving this equation gave you p = 1/10, which in turn meant that 1−p (the steady-state probability of passing through the right slot) was 9/10.

Applying these values to the subsequent row with three slots, the probability of passing through the leftmost slot was p/4, or 1/40; the probability of passing through the middle slot was p/2 + 1/4, or 3/10; and the probability of passing through the rightmost slot was 3/4 − 3/4·p, or 27/40. To land in the bucket labeled A in the original diagram, the ball had to pass through a leftmost slot, which meant the solution was 1/40.

If you gave an answer very close to 1/40, or 2.5 percent—for instance, if you used the original diagram with 12 rows of pins rather than one with infinitely many—I still gave you full credit.

Careful readers will recognize that we haven’t actually proven the answer was 1/40, because we haven’t proven the bean machine actually converged to a steady state. One way to prove the result is to write the probability of passing through the left slot in a given two-slot row as 1/10+k. Using the general formulas we already found, the probability of passing through the left slot two rows later was 3/8·(1/10+k)+1/16, which simplified to 1/10+3/8·k. So every two rows, the value of k was reduced by a factor of 3/8, which meant the probability did indeed converge to 1/10.

Finally, a few solvers, including Mike Porter (winner of last week’s Extra Credit, below), found the probability the ball would land in bucket A when the leftward bias of the pins was 𝛼 (which happened to be 1/4 in the original puzzle). According to Mike, that general probability was 𝛼³/[𝛼²+(1−𝛼)²], which indeed was 1/40 when 𝛼 = 1/4.

Last Week’s Extra Credit

Congratulations to the (randomly selected) winner from last week: 🎻 Mike Porter 🎻 from Haddenham, United Kingdom. I received 30 timely submissions, of which 26 were correct—good for an 87 percent solve rate.

For Extra Credit, you considered the board below, which started with a row with six pins (and five slots), followed by a row with five pins (and six slots), and then back to six pins in an alternating pattern. Balls were only allowed to enter through the middle three slots on top. This time around, the pins that weren’t on the far left or far right behaved normally, meaning each ball was equally likely to go around it via the left side or the right side.

Your goal was to create a trapezoidal distribution along one of the rows with six slots, highlighted with dotted lines in the diagram above. More precisely, the frequency of balls passing through the six slots from left to right had to be x−y, x, x+y, x+y, x, x−y, for some values of x and y with x ≥ y.

Suppose the ratio by which you dropped balls into the top three middle slots, from left to right, was a : b : c, with a + b + c = 1. What were all the ordered triples (a, b, c) that resulted in a trapezoidal distribution in at least one row with six slots?