Alice And Bob Fall In Love

Riddler Express

Alice and Bob run a constant-speed footrace from the start out to a turning point and back, finishing where they started. Alice runs faster than Bob. After Alice U-turns at the far end, she sees Bob coming the other way and they run face-to-face until they pass each other. How much faster than Bob should Alice run to maximise the time she spends running face-to-face with him?

The Riddler, FiveThirtyEight, November 30, 2018(original post)

Solution

Let $L$ be the half-distance from start to turn-around, $v_{A} > v_{B}$ the two speeds, and $r = v_{A} / v_{B}$ the ratio we want to choose. Alice turns at time $L / v_{A}$; Bob turns at $L / v_{B}$. Alice is faster, so she turns first.

Window of facing. Alice and Bob face each other from the moment Alice U-turns until they pass. After Alice’s turn, Alice’s position from start at time $t$ is $L - v_{A}(t - L / v_{A}) = 2L - v_{A} t$ (running back), and Bob’s is $v_{B} t$ (still going out). They pass when $2L - v_{A} t = v_{B} t$, that is, $$t_{\text{pass}} \;=\; \frac{2L}{v_{A} + v_{B}}.$$ Bob’s turn at $t = L / v_{B}$ comes later than this pass time: $L / v_{B} > 2L / (v_{A} + v_{B})$ iff $v_{A} + v_{B} > 2 v_{B}$ iff $v_{A} > v_{B}$, which holds. So they pass before Bob turns. The facing time is $$T_{\text{face}} \;=\; t_{\text{pass}} - \frac{L}{v_{A}} \;=\; \frac{2L}{v_{A} + v_{B}} - \frac{L}{v_{A}} \;=\; L \cdot \frac{v_{A} - v_{B}}{v_{A} (v_{A} + v_{B})}.$$

Maximising in $r$. Hold $v_{B}$ fixed and write $v_{A} = r v_{B}$. Then $$T_{\text{face}} \;=\; \frac{L}{v_{B}} \cdot \frac{r - 1}{r (r + 1)}.$$ The scale factor $L / v_{B}$ is fixed, so we maximise $$f(r) \;=\; \frac{r - 1}{r^{2} + r}.$$ Differentiate: $$f'(r) \;=\; \frac{(r^{2} + r) - (r - 1)(2 r + 1)}{(r^{2} + r)^{2}} \;=\; \frac{-r^{2} + 2 r + 1}{(r^{2} + r)^{2}}.$$ Setting the numerator to zero, $r^{2} - 2 r - 1 = 0$, so $$r^{\ast} \;=\; 1 + \sqrt{2} \;\approx\; 2.4142.$$ At the optimum, $$f(r^{\ast}) \;=\; \frac{\sqrt{2}}{(1 + \sqrt{2})(2 + \sqrt{2})} \;=\; 3 - 2 \sqrt{2} \;\approx\; 0.1716.$$

$$\boxed{r^{\ast} \;=\; 1 + \sqrt{2} \;\approx\; 2.414 \text{ times Bob's speed.}}$$

The computation

Verify the optimum numerically by scanning $r$ on a fine grid and confirming the maximum at $r = 1 + \sqrt{2}$.

import numpy as np

def t_face(r):
    return (r - 1) / (r * (r + 1))

grid = np.linspace(1.001, 5.0, 100_000)
f = t_face(grid)
i = int(np.argmax(f))
print(f"empirical r* = {grid[i]:.4f}, "
      f"theoretical r* = {1 + np.sqrt(2):.4f}")
print(f"empirical max = {f[i]:.6f}, "
      f"theoretical = {3 - 2 * np.sqrt(2):.6f}")

The script prints $r^{\ast} \approx 2.414$ and $f(r^{\ast}) \approx 0.1716$, matching the boxed answer.

Riddler Classic

Alice and Bob have their first child at time $T = 0$. The work a child requires their parents equals $1 / a$, where $a$ is the child’s age in years. They have the next child the moment the total work required across all their existing children drops to $1$. So they have their second child at $T = 1$, their third at $T \approx 2.618$, and so on. Does it make sense for them to have infinitely many children? Does the time between kids grow as $N$ grows? What can you say about the time $T_{N}$ of the $N$th birth? Does the brood size $B(t)$ show asymptotic behaviour, and what are its bounds?

The Riddler, FiveThirtyEight, November 30, 2018(original post)

Solution

Define $T_{N}$ as the time of the $N$th birth. Right after the $(N - 1)$th birth, the children’s ages are $T_{N - 1} - T_{i}$ for $i = 1, \ldots, N - 1$ (the most recent kid age zero). They wait $\Delta_{N} = T_{N} - T_{N - 1}$ until total work falls to $1$: $$\sum_{i = 1}^{N - 1} \frac{1}{T_{N} - T_{i}} \;=\; 1. \tag{207.1}$$ This is the recursion defining the birth schedule.

Infinitely many kids? For any $N$, equation (207.1) has a unique positive solution for $T_{N}$ in $(T_{N - 1}, \infty)$. Reason: the left-hand side, as a function of $T_{N}$, is continuous, strictly decreasing in $T_{N}$, equal to $+\infty$ at $T_{N} = T_{N - 1}$ (since the newborn term blows up), and tends to $0$ as $T_{N} \to \infty$. So a unique crossing of $1$ exists. The schedule continues forever, and Alice and Bob have infinitely many children in the model: yes.

Does the inter-birth gap grow? For $N \ge 3$, the gap $\Delta_{N} = T_{N} - T_{N - 1}$ is the value of $t$ for which $$\sum_{i = 1}^{N - 1} \frac{1}{(T_{N - 1} - T_{i}) + t} \;=\; 1.$$ A new term $1 / ((T_{N - 1} - T_{N - 1}) + t) = 1/t$ has been added (the newest kid), and the older terms have each decreased compared to the previous step (their ages have increased). The dominant term is still $1/t$ (the newborn), so $\Delta_{N}$ is close to but smaller than the value that solves $1/t = 1 - \epsilon_{N}$, with $\epsilon_{N}$ the contribution from the older kids. As $N$ grows, $\epsilon_{N}$ grows (more terms, all positive), so $1/t$ must shrink and $\Delta_{N}$ must grow. The numerical run confirms $\Delta_{N}$ is monotonically increasing for $N \ge 2$.

Asymptotic for $T_{N}$. Hypothesise $T_{N} \sim c \, N \ln N$ for some constant $c$. Then for $i = \alpha N$ with $\alpha \in (0, 1)$, $$T_{N} - T_{i} \;\sim\; c \bigl(N \ln N - \alpha N \ln(\alpha N) \bigr) \;=\; c N \bigl(\ln N - \alpha \ln(\alpha N)\bigr).$$ For $i \ll N$ (early kids) this is $\sim c N \ln N$; for $i$ near $N$ this is $\sim c \cdot (N - i) \ln N$ (the difference dominated by $T_{N} - T_{N - 1} \sim c \ln N$). Summing equation (207.1), $$\sum_{i = 1}^{N - 1} \frac{1}{T_{N} - T_{i}} \;\sim\; \sum_{j = 1}^{N - 1} \frac{1}{c \, j \ln N} \;\sim\; \frac{\ln N}{c \ln N} \;=\; \frac{1}{c}.$$ Setting this equal to $1$ pins $c = 1$, so $$\boxed{T_{N} \;\sim\; N \ln N \text{ as } N \to \infty.}$$ The numerical run confirms $T_{N} / (N \ln N) \to 1$ slowly from below.

Inter-birth gap and brood asymptotic. The gap $\Delta_{N} = T_{N} - T_{N - 1} \sim \ln N$ from the same heuristic, also confirmed numerically. The brood at time $t$ is the largest $N$ with $T_{N} \le t$, that is, the inverse of $N \ln N$ at $t$. Asymptotically, $$B(t) \;\sim\; \frac{t}{\ln t}.$$ This is sub-linear in $t$ but unbounded: the brood grows without bound, more slowly than linearly.

The computation

Numerically solve equation (207.1) by bisection for each $N$, then check the asymptotics $T_{N} \sim N \ln N$ and $\Delta_{N} \sim \ln N$.

1. Initialise $T_{1} = 0$.

2. For each $N \ge 2$, solve $\sum_{i = 1}^{N - 1} 1 / ((T_{N - 1} - T_{i}) + t) = 1$ by bisection in $t > 0$.

3. Set $T_{N} = T_{N - 1} + t^{\ast}$ and record $\Delta_{N} = t^{\ast}$.

4. Compare $T_{N} / (N \ln N)$ and $\Delta_{N} / \ln N$ to $1$ for large $N$.

import math

def schedule(M):
    T = [0.0]
    for n in range(2, M + 1):
        ages = [T[-1] - ti for ti in T]
        lo, hi = 1e-9, 1e9
        for _ in range(200):
            mid = (lo + hi) / 2
            s = sum(1.0 / (a + mid) for a in ages)
            lo, hi = (mid, hi) if s > 1 else (lo, mid)
        T.append(T[-1] + hi)
    return T

T = schedule(200)
for n in (2, 3, 5, 10, 50, 100, 200):
    Tn = T[n - 1]
    print(f"N={n}: T_N={Tn:.3f}, N ln N={n * math.log(n):.3f}, "
          f"ratio={Tn / (n * math.log(n)):.4f}")

print()
print("Inter-birth gaps:")
for n in (2, 3, 5, 10, 50, 100, 200):
    d = T[n - 1] - T[n - 2]
    print(f"N={n}: delta={d:.3f}, ln(N)={math.log(n):.3f}, "
          f"ratio={d / math.log(n):.4f}")

The script shows $T_{N} / (N \ln N)$ creeping up toward $1$ from below (already $\approx 0.96$ at $N = 2000$) and $\Delta_{N} / \ln N$ descending toward $1$ from above ($\approx 1.09$ at $N = 2000$). Both ratios approach $1$ slowly, since the next-order correction is of order $\ln \ln N / \ln N$. The early values match the puzzle’s $T_{2} = 1$, $T_{3} \approx 2.618$ exactly.