How Fast Can You Deliver PB&Js? How Many Meerkats Can Survive?

Riddler Express

You deliver peanut-butter-and-jelly sandwiches from a restaurant at $20$th Street and Avenue F in Riddler City. The grid has $61$ east-west streets ($1$st to $61$st) and $21$ north-south avenues (A to U), with each block $0.1$ miles long. The speed limit is $20$ mph everywhere, except Avenue U (the Ultra-Speed Trafficway) at $200$ mph. For which destinations does it pay to detour to Avenue U? (No traffic, no turn losses.)

The Riddler, FiveThirtyEight, July 6, 2018(original post)

Solution

Index streets $r = 1, \ldots, 61$ and avenues $c = 1, \ldots, 21$ (so A $= 1$, F $= 6$, U $= 21$). Each block is $0.1$ miles. At $20$ mph a block takes $0.1 / 20 \cdot 60 = 0.3$ minutes; on Avenue U at $200$ mph a block takes $0.03$ minutes. You start at $(r_0, c_0) = (20, 6)$.

Direct route. Drive Manhattan-style on surface streets. Time $$T_{\text{direct}}(r, c) \;=\; 0.3 \, (|r - 20| + |c - 6|).$$

Avenue-U route. Drive east to Avenue U ($15$ blocks at $20$ mph), then north or south along U ($|r - 20|$ blocks at $200$ mph), then west back to avenue $c$ ($21 - c$ blocks at $20$ mph). Time $$T_{\text{U}}(r, c) \;=\; 0.3 \, (15 + 21 - c) \;+\; 0.03 \, |r - 20|.$$ (If $c = 21$ you skip the westward leg.)

Avenue U pays whenever $T_{\text{U}} < T_{\text{direct}}$: $$0.3 \cdot (15 + 21 - c) + 0.03 \, |r - 20| \;<\; 0.3 \, (|r - 20| + |c - 6|),$$ which rearranges to $$|r - 20| \;>\; \frac{4.5 + 0.3 \,(21 - c) - 0.3 \,|c - 6|}{0.27}.$$ The right-hand side is a function of $c$ alone; call it the distance-from-20th threshold $\theta(c)$. The pattern is:

Read this geometrically. Streets only go up to $61$, that is $41$ blocks north of you and $19$ blocks south. So for $c \in \{$A, B, C, D, E, F$\}$ (the western strip) Avenue U pays only for destinations more than $33.33$ blocks away from $20$th Street, that is for street numbers above $53$rd to the north (south is impossible: only $19$ blocks down). Moving east, the threshold drops linearly: by Avenue M ($c = 13$) you save by detour for anything more than $17.78$ blocks away, that is street $\le 2$ or street $\ge 38$. By Avenue T ($c = 20$) you save almost everywhere off your home row.

The computation

Encode the grid, compute both route times for every address, and confirm the boundary by exhaustive enumeration.

def t_direct(r, c):
    return 0.3 * (abs(r - 20) + abs(c - 6))

def t_via_U(r, c):
    if c == 21:
        return 0.3 * 15 + 0.03 * abs(r - 20)
    return 0.3 * 15 + 0.03 * abs(r - 20) + 0.3 * (21 - c)

faster = 0
boundary = {}
for r in range(1, 62):
    for c in range(1, 22):
        if (r, c) == (20, 6):
            continue
        if t_via_U(r, c) < t_direct(r, c):
            faster += 1
for c in range(1, 22):
    boundary[c] = min(
        (abs(r - 20) for r in range(1, 62)
         if t_via_U(r, c) < t_direct(r, c)),
        default=None,
    )

print("addresses where Avenue U is faster:", faster)
print("boundary |r-20| per column (None = never):")
for c in range(1, 22):
    print(f"  c={c:2d} ({chr(ord('A')+c-1)}): {boundary[c]}")

The script prints addresses where Avenue U is faster: 532 (out of $61 \cdot 21 - 1 = 1280$) and the per-avenue boundary $|r - 20|$, matching the analytic thresholds above. The qualitative answer: use Avenue U for deliveries that are far north (and slightly far south on the eastern side); stay on surface streets near home.

Riddler Classic

Meerkats eat scorpions. Without meerkats the scorpion population doubles every month; without scorpions the meerkat population halves every month; at $20$ scorpions and $5$ meerkats both populations are stable. Use the Lotka-Volterra model for predator and prey.

(a) How many meerkats are there when the scorpion population is at its maximum? (b) How many of each are there when the meerkat population is increasing by $4$ per month and the scorpion population is decreasing by $2$ per month? (c) Starting from $100$ scorpions and $10$ meerkats, what is the largest the meerkat population gets, and how long until both populations return to their starting values?

The Riddler, FiveThirtyEight, July 6, 2018(original post)

Solution

Let $x$ be the scorpion population, $y$ the meerkat population, $t$ time in months. The Lotka-Volterra equations are $$\frac{dx}{dt} \;=\; a x - b x y, \qquad \frac{dy}{dt} \;=\; d x y - c y.$$

Fitting parameters. With $y = 0$: $dx/dt = a x$, so $x(t) = x_0 e^{a t}$. Doubling each month means $e^{a} = 2$, hence $a = \ln 2$. With $x = 0$: $dy/dt = -c y$, so $y$ halves each month means $e^{-c} = 1/2$, hence $c = \ln 2$. The equilibrium $(dx/dt, dy/dt) = (0, 0)$ at $(x, y) = (20, 5)$ gives $a = b y = 5 b$ and $c = d x = 20 d$, so $$b \;=\; \frac{\ln 2}{5}, \qquad d \;=\; \frac{\ln 2}{20}.$$

(a) Maximum scorpions. Along any trajectory $x$ reaches a maximum when $dx/dt = 0$, that is when $a = b y$, that is when $$y \;=\; \frac{a}{b} \;=\; 5 \text{ meerkats.}$$ By symmetry the meerkat maximum sits at $x = c/d = 20$ scorpions. $$\boxed{\;y \;=\; 5 \text{ meerkats at peak scorpions.}\;}$$

(b) The prescribed rates. Set $dx/dt = -2$ and $dy/dt = +4$: $$x (a - b y) \;=\; -2, \qquad y (d x - c) \;=\; +4.$$ From the first, $b y = a + 2/x$, so $y = (a + 2/x) / b = 5 + 10/(\ln 2 \cdot x)$. From the second, $d x = c + 4/y$, so $x = (c + 4/y) / d = 20 + 80/(\ln 2 \cdot y)$. Substituting and solving numerically gives $$\boxed{\;x \;\approx\; 41.59 \text{ scorpions}, \quad y \;\approx\; 5.35 \text{ meerkats.}\;}$$ (Fractional animals are an artefact of the continuous model.)

(c) Extra credit: orbit from $(100, 10)$. Lotka-Volterra trajectories are closed orbits around the equilibrium $(20, 5)$, with conserved quantity $$H(x, y) \;=\; d x - c \ln x \;+\; b y - a \ln y.$$ The starting point $(100, 10)$ fixes $H$ and the orbit. The peak meerkat population on the orbit is found by setting $dy/dt = 0$ along the orbit ($x = 20$) and using $H(100, 10) = H(20, y_{\max})$. Numerically integrating gives $y_{\max} \approx 26.9$ meerkats and the orbit period $\approx 13.45$ months. Both values are reproduced in the computation block. $$\boxed{\;y_{\max} \;\approx\; 27, \quad T \;\approx\; 13.45 \text{ months.}\;}$$

The computation

Integrate the Lotka-Volterra ODE numerically with the fitted parameters, read off the equilibrium conditions in (a) and (b), and measure the orbit in (c).

import math
import numpy as np
from scipy.integrate import odeint
from scipy.optimize import fsolve

a = math.log(2)
c = math.log(2)
b = a / 5
d = c / 20

# (b) solve for (x, y) given dx/dt = -2, dy/dt = +4
def eqs(v):
    x, y = v
    return [x * (a - b * y) + 2, y * (d * x - c) - 4]
xb, yb = fsolve(eqs, [40, 5])
print(f"(b) scorpions={xb:.3f}, meerkats={yb:.3f}")

# (c) orbit from (100, 10)
def rhs(state, t):
    x, y = state
    return [a * x - b * x * y, d * x * y - c * y]

t = np.linspace(0, 30, 200_000)
sol = odeint(rhs, [100, 10], t)
xs, ys = sol[:, 0], sol[:, 1]
print(f"(c) max meerkats = {ys.max():.3f}")
# Period: return to (100, 10)
dist = np.sqrt((xs - 100) ** 2 + (ys - 10) ** 2)
i = np.argmin(dist[len(t) // 10:]) + len(t) // 10
print(f"(c) orbit period = {t[i]:.3f} months")

The script prints $(x, y) \approx (41.59, 5.35)$, $y_{\max} \approx 26.9$, and orbit period $\approx 13.45$ months, matching the boxed answers.