This week the #puzzle is: Can You Hop in a Spiral? #geometry #trigonometry #angle #arctan #minimize #markovchain #coding

Frankie the frog is hopping on a large, packed grid of lily pads, shown below. The pads are circular and each is a distance 1 from its nearest neighbors. (More concretely: Each pad has a diameter of 1 and they are arranged in a hexagonal lattice.) Frankie starts at (0, 0), the center of the pad labeled A. Then she hops due east to pad B at (1, 0), and from there she hops to pad C at (1.5, √(3)/2).

She wants to continue hopping in a counterclockwise, spiral-like pattern. Each of her jumps is to the center of a neighboring pad, a net distance of 1. But there are two rules her spiral must follow:

– Each next pad must be in a more counterclockwise direction (relative to spiral’s origin at pad A) than the previous pad. – Each pad must be farther from A than the previous pad.

After a number of hops spiraling around, Frankie realizes she is, once again, due east from A. What is the closest to A she could possibly be? That is, what is the minimum possible distance between the center of the pad she’s currently on from the center of pad A?

And for extra credit:

Frankie has stored all of her food on lily pad A. However, her food has a tendency to “fly” away. Every second, the food that’s on every lily pad splits up into six equal portions that instantaneously relocate to the six neighboring pads.

At zero seconds, all the food is on lily pad A. After one second, there’s no food on pad A, and 1/6 of the food is on each of the surrounding six pads. After two seconds, 1/6 of the food is again on pad A, while the rest of the food is elsewhere.

After how many seconds N (with N > 2) will pad A have less than 1 percent of its original amount?

Can You Hop in a Spiral?

Highlight to reveal (possibly incorrect) solution:

Desmos 1 Program Desmos 2

Method 1:

• I try to construct the path in Desmos. At every step, is it possible to turn 60° counter clockwise and still obey the rules? If not, continue straight ahead.
• There are just too many steps!

Method 2:

• I write a program to assist. I look at all 6 directions. But I also know which 2 are 60° counter clockwise and straight ahead. I look at the distance and the angle. And then I choose.
• I reuse Desmos to show the result.
• I end up at a distance 64.

Method 3:

• I can vaguely see a method, where I keep going straight ahead, until I reach x = 0, y = x/2k or y = – x/2k. (k = √3/2.) (These guide lines are also shown in Desmos.) Let’s try it out. Desmos 2 assists.
• I want my spiral to be as tight as possible. From any point, I test going back the same way, or 60° less, or 120° less, or 180° less, or 240° less, or 300° less, in that order. I am looking for small additions to the distance to A, hopefully getting large jumps in angle.
• |AX| denotes the distance between points A and X, where points A and X are the centers of pads A and X. α_X denotes the angle to point A from X.
• Looking for D.
  • From C = (1.5,k) I could go back to D0 = B. But |AD0| = |AB| < |AC|, as the rules state. Likewise α_D0 = α_B < α_C, as the rules state. Rejected.
  • I could go to D1. But |AD1| < |AC|. Rejected.
  • I could go to D2. |AC| = 1.73, |AD2| = 2. α_C = 30°, α_D2 = 60°.
  • I could go to D3. |AD3| = 2.65. α_D3 = 40.89°. D2 would be better, more angle, less distance.
  • I could go to D4. α_D4 = 19.11°. Rejected.
  • I could go to D5. α_D5 = 0°. Rejected.
• I choose D = D2 = (1,2k). |AD| = 2. α_D = 60°.
• The line through C and D crosses y = x/2k in C. It is y = -2kx + 4k.
• Looking for E.
  • E1 = D1. |AE1| = |AD1| < |AC| < |AD|. Rejected.
  • E2. |AE2| < |AD|. Rejected.
  • E3. |AE3| = 2.65. α_E3 = 79.11°.
  • E4. α_E4 = 60°. Not smaller than α_D. Rejected.
  • E5 = D3. α_E5 = 40.89°. Rejected.
• There’s only 1 choice, E3 = E = (0.5,3k). |AE| = 2.65. α_E = 79.11°.
• Looking for F. F1 fails both distance and angle. F2 has the same distance. F3 is okay. F4 and F5 both fail the angle rule. So I choose F3 = F = (0,4k). I am now on the line x = 0 and the line y = 4k.
• Going forward, I will choose G3, H3 etc. until I reach L3, on the line y = – x/2k. All these points are on the line y = 4k. Then I will turn left a little, choosing M2. And then go straight forward a bit.
• Let’s look at some of these distances a bit more detailed.
• Being in D = (1,2k), on the line y = -2kx + 4k, I am looking for E.
  • |AD|² = 1² + (2k)²
  • E1 = D + (-0.5,-k).
  • |AE1|² = (1-0.5)² + (2k-k)² < 1² + (2k)² = |AD|²
  • E2 = D + (-1,0).
  • |AE2|² = (1-1)² + (2k+0)²
    • = 1² – 2*1*1 + 1² + (2k)²
    • = 1² + (2k)² – 2*1*1 + 1²
    • = |AD|² – 2*1*1 + 1²
    • = |AD|² – 2 + 1
    • = |AD|² – 1
    • < |AD|²
  • E3 = D + (-0.5,k)
  • |AE3|² = (1-0.5)² + (2k+k)²
    • = 1² – 2*1*0.5 + 0.5² + (2k)² + 2*2k*k + k²
    • = 1² + (2k)² – 2*1*0.5 + 0.5² + 2*2k*k + k²
    • = |AD|² – 2*1*0.5 + 0.5² + 2*2k*k + k²
    • = |AD|² – 1 + 0.5² + 4k² + k²
    • = |AD|² – 0.75 + 5k²
    • = |AD|² + 3
  • Distance wise, E3 is the only candidate. (E4 and E5 are rejected because of the angle.)
• For a more general case, let’s look at the search for H, I etc.
• X = (x, 4k), x < 0
• Y1 = (x+0.5, 4k-k)
• Y2 = (x-0.5, 4k-k)
• Y3 = (x-1, 4k)
• Y4 = (x-0.5, 4k+k)
• Y5 = (x+0.5, 4k+k)
• |AX|² = x² + (4k)²
• |AY1|² = (x+0.5)² + (4k-k)²
  • = x² + 2*0.5*x + 0.5² + (4k)² – 2*4k*k + k²
  • = x² + (4k)² + 2*0.5*x + 0.5² – 2*4k*k + k²
  • = |AX|² + 2*0.5*x + 0.5² – 2*4k*k + k²
  • = |AX|² + x + 0.5² – 8k² + k²
  • = |AX|² + x + 0.5² – 7k²
• We want |AX|² < |AY1|²
  • <=> |AX|² < |AX|² + x + 0.5² – 7k²
  • <=> 0 < x + 0.5² – 7k²
  • <=> – 0.5² + 7k² < x
  • <=> – 0.25 + 7*(√3/2)² < x
  • <=> – 0.25 + 7 * 3/4 < x
  • <=> 5 < x
• But x < 0, so that won’t happen.
• |AY2|² = (x-0.5)² + (4k-k)²
  • = x² – 2*0.5*x + 0.5² + (4k)² – 2*4k*k + k²
  • = x² + (4k)² – 2*0.5*x + 0.5² – 2*4k*k + k²
  • = |AX|² – 2*0.5*x + 0.5² – 2*4k*k + k²
  • = |AX|² – x + 0.5² – 8k² + k²
  • = |AX|² – x + 0.5² – 7k²
• We want |AX|² < |AY2|²
  • <=> |AX|² < |AX|² – x + 0.5² – 7k²
  • <=> 0 < – x + 0.5² – 7k²
  • <=> x < 0.5² – 7k²
  • <=> x < 0.25 – 7*(√3/2)²
  • <=> x < 0.25 – 7 * 3/4
  • <=> x < -5
• This should certainly happen at some point, say x = -6. In that case we would have M2 = (-6.5, 3k).
• Let’s also look at Y3.
• |AY3|² = (x-1)² + (4k)²
  • = x² – 2x + 1 + (4k)²
  • = x² + (4k)² – 2x + 1
  • = |AX|² – 2x + 1
• We want |AX|² < |AY3|²
  • <=> |AX|² < |AX|² – 2x + 1
  • <=> 0 < – 2x + 1
  • <=> 2x < 1
  • <=> x < 0.5
• We already have that as x < 0.
• The turn to M2 happens at L3 = (-6, 4k).
  • x = -6
  • k = √3/2
  • 1/k = 2/√3
    • = 2√3/3
  • Does L3 lie on y = – x/2k?
  • y = – (-6) / (2k)
    • = 6/2k
    • = 6 * 2√3/3 / 2
    • = 6 * √3/3
    • = 2 * √3
    • = 4 * √3/2
    • = 4k
  • Yes, it does.
• I think I need some more details here. But they should be trivial.
• Sketch: Rotate the situation around A. L3 is now on x = 0. Do similar calculations. Etc.
• In conclusion: Within the guide lines, travelling on a line perpendicular to x = 0, y = x/2k or y = – x/2k, it is safe to turn left when a guide line is hit.

And for extra credit:

Spreadsheet

Method 1:

• I fiddle around with a spreadsheet, just to see what happens.
• There are just too many steps!

Method 2:

• I write a program. Markov chain like.
• I end up with N = 28.