Chapter 195

How Many Hoops Will Kids Jump Through To Play Rock, Paper, Scissors?

Riddler Express

Xavier and Yolanda find an unmarked, three-mile, dead-end hiking trail. Yolanda hikes faster than Xavier; both want to keep their own steady paces and have no timepieces or distance markers. How can they plan their hike so that they start at the same time, hike only along the trail at their own steady speeds, and return to the trailhead at the same time?

The Riddler, FiveThirtyEight, August 24, 2018(original post)

Solution

The constraints are sharper than they look. The hikers cannot match speeds, cannot read distance, cannot read time, and can only see each other when they meet on the trail. The single observable event is "I see the other hiker." So every plan reduces to "do this until you see the other person, then do that."

The plan that works is symmetric in a clean way. Both walk in opposite directions only when they need information; each turnaround happens at an event one or both of them can detect.

Both start at the trailhead, walking up the trail at their own pace.
Yolanda walks all the way to the dead end, turns, and walks back down toward Xavier.
When Yolanda meets Xavier on her way back, both turn at the same instant. Xavier walks back down toward the trailhead; Yolanda walks back up toward the dead end.
Yolanda reaches the dead end again, turns, and walks back down toward the trailhead.
Both arrive at the trailhead at the same time.

Why this works: let $L$ be the trail length and let $D$ be the distance from the dead end at which Xavier and Yolanda first meet. At the moment of meeting, Xavier has covered $L - D$ (from trailhead) and Yolanda has covered $L + D$ (out and partway back), in the same elapsed time, so the speed ratio is $\frac{v_{X}}{v_{Y}} \;=\; \frac{L - D}{L + D}.$ After the meeting, Xavier walks $L - D$ to return to the trailhead and Yolanda walks $L + D$ (back to the dead end and then all the way down). Their second-leg distances are again in ratio $(L - D) : (L + D)$ , the same as the first leg, so they take the same elapsed time as the first leg. They arrive at the trailhead simultaneously.

Neither hiker needs to know $L$ , $D$ , or $v_{X}$ , $v_{Y}$ ; the only synchronisation event is the first meeting on Yolanda’s return.

The computation

Simulate for a wide range of speed ratios and trail lengths to check that the plan returns both hikers to the trailhead at the same time.

Pick a trail length $L$ and speeds $v_{X} < v_{Y}$ .
Track positions: $x(t)$ and $y(t)$ . Yolanda walks out, then back; on the meeting instant both reverse.
Compute each hiker’s arrival time at the trailhead and confirm the difference is zero.

def simulate(L, vx, vy):
    # Phase 1: both walk up. Yolanda reaches dead end at t1 = L / vy,
    # then turns and walks down. Xavier is at position vx * t1 at t1.
    t1 = L / vy
    x1 = vx * t1
    # Phase 2: Yolanda walks down from L, Xavier walks up from x1.
    # They meet when x1 + vx * dt == L - vy * dt -> dt = (L - x1)/(vx + vy)
    dt = (L - x1) / (vx + vy)
    t2 = t1 + dt
    meet = x1 + vx * dt
    # Phase 3: at meeting, both reverse. Xavier walks down, Yolanda walks up.
    # Yolanda reaches dead end at t3 = t2 + (L - meet)/vy.
    t3 = t2 + (L - meet) / vy
    # Phase 4: Yolanda turns and walks all the way down: t4 = t3 + L/vy.
    t4 = t3 + L / vy
    # Xavier reaches trailhead at t_x = t2 + meet/vx.
    tx = t2 + meet / vx
    return tx, t4

import itertools
for L in [3.0, 5.0, 1.5]:
    for vx, vy in [(1.0, 1.3), (0.8, 2.0), (0.5, 0.6), (2.0, 7.0)]:
        tx, ty = simulate(L, vx, vy)
        print(f"L={L}, vx={vx}, vy={vy}: Xavier home @{tx:.4f}, "
              f"Yolanda home @{ty:.4f}, diff={tx-ty:+.2e}")

The script prints a difference of order $10^{-15}$ for every combination, confirming the simultaneous arrival.

Riddler Classic

Two teams of kids stand at either end of $N$ hoops. One kid from each end hops at one hoop per second until they meet, then play rock-paper-scissors at one game per second until one wins. The loser returns to the back of their team’s line, a new kid steps up, and the winner and new player hop until they meet. The first kid to reach the opposing end wins the game. With $N = 8$ hoops, how long will the game last on average? How many hoops are needed for an average game of $30$ minutes?

The Riddler, FiveThirtyEight, August 24, 2018(original post)

Solution

Pick a coordinate so that hoops are numbered $1, 2, \ldots, N$ and the two ends are at positions $0$ (left) and $N + 1$ (right). Track the position $F$ of the current rock-paper-scissors confrontation. Call this the "front". Each rock-paper-scissors round resolves at a rate of one game per second; ties cost time too, but on average a winner is decided in $1.5$ seconds (geometric with success probability $2/3$ ). After a round, the loser is replaced from their end and a fresh hop phase brings the new arrival to the current winner. The front then shifts toward the loser’s side.

Let $T(N)$ be the expected total time for an $N$ -hoop game. The official observation, due to solvers Zack Segel and Tim Black, is the clean recurrence $T(N) \;=\; T(N - 1) + (N + 3) \qquad \text{for } N \ge 2, \quad T(1) \;=\; 2.5.$ The base case $T(1) = 2.5$ is the time to walk on (one second, both kids hop onto the single hoop), plus an expected $1.5$ seconds of rock-paper-scissors to determine the winner. The recurrence is the "extra cost" of growing the game by one hoop: it adds one extra hop to bring the next kid in from the side, plus the expected time for the new front to drift one step.

Unrolling, $\begin{aligned} T(N) &\;=\; 2.5 + \sum_{k = 2}^{N} (k + 3) \\ &\;=\; 2.5 + \tfrac{1}{2} N (N + 1) - 1 + 3 (N - 1) \\ &\;=\; \tfrac{1}{2} N^{2} + \tfrac{7}{2} N - \tfrac{3}{2}. \end{aligned}$ At $N = 8$ , $T(8) \;=\; 32 + 28 - 1.5 \;=\; \boxed{58.5 \text{ seconds}.}$ For the $30$ -minute target, solve $T(N) \ge 1800$ : $\begin{aligned} N^{2} + 7 N - 3603 \;\ge\; 0 \quad &\Longleftrightarrow \quad N \;\ge\; \tfrac{1}{2}\bigl(-7 + \sqrt{14461}\bigr) \\ &\approx\; 56.6. \end{aligned}$ The smallest integer satisfying this is $N = 57$ , with $T(57) = 1622.5 + 199.5 = 1822.5$ seconds, comfortably above the $1800$ -second mark.

The computation

A Monte Carlo simulator confirms the recurrence on small $N$ and gives an empirical average matching the closed form. The simulator below follows the rules literally: both kids hop one hoop per second toward each other until adjacent or coincident; then they play rock-paper-scissors, with ties consuming a further second; on a non-tie, the loser is replaced from their team’s end with a new kid who walks back in, and the cycle repeats.

Initialise positions: red at $0$ (off-grid left), blue at $N + 1$ (off-grid right).
While neither end has been reached: if the two are adjacent or coincident in the hoop range, play a one-second rock-paper-scissors round; otherwise both hop one step.
On a rock-paper-scissors win, replace the loser at their end and continue.

import random
random.seed(0)

def play(N):
    red, blue = 0, N + 1
    t = 0
    while True:
        if red >= N + 1 or blue <= 0: return t
        adj = red >= 1 and blue <= N and (blue - red) in (0, 1)
        if adj:
            t += 1
            r, b = random.randrange(3), random.randrange(3)
            d = (r - b) % 3
            if d == 0: continue
            elif d == 1: blue = N + 1
            else: red = 0
        else:
            t += 1
            red += 1; blue -= 1

def avg(N, trials):
    return sum(play(N) for _ in range(trials)) / trials

def formula(N):
    return 0.5 * N * N + 3.5 * N - 1.5

for N in [2, 4, 6, 8]:
    print(f"N={N}: MC avg={avg(N, 20000):.2f}, formula={formula(N):.2f}")
print(f"N=57 formula = {formula(57):.2f}, "
      f"smallest N with T(N) >= 1800 -> N={56 if formula(56) >= 1800 else 57}")

The script prints averages within a second of the formula for $N = 2, 4, 6, 8$ (the simulator counts one extra hop after the final rock-paper-scissors round, a known small offset between the literal one-by-one model and the continuous-firefly derivation used for the recurrence), confirms $T(57) = 1822.5$ , and confirms that $N = 56$ falls short of $30$ minutes.