Can You Reach The Beach?

The Riddler for August 7, 2020. The Express traces the set of island points with more than one nearest shore point, the medial axis. The Classic invents an addition that breeds nematodes and asks for the expected value of a power.

Riddler Express

Euclid Island is a $3 \times 2$ rectangle. A hiking trail connects exactly those points from which two or more distinct shore points are tied for nearest. What is the total length of the trail? Extra credit: the same question for elliptical Al-Battani Island, with major axis $3$ and minor axis $2$.

The Riddler, FiveThirtyEight, August 7, 2020(original post)

Solution

Grow a circle centred at your position until it first touches the shore: you are on the trail exactly when it touches in two or more places. This set is the region’s medial axis (its skeleton).

For the rectangle, put the corners at $(0,0)$, $(3,0)$, $(3,2)$, $(0,2)$. A point equidistant from the two long sides lies on the centre line $y = 1$; one equidistant from a short side and a long side lies on a $45^\circ$ diagonal from a corner. The skeleton is a central horizontal segment plus four diagonals from its ends to the corners. The central segment runs from $(1,1)$ to $(2,1)$, length $3 - 2 = 1$. Each diagonal, say $(0,0)$ to $(1,1)$, has length $\sqrt{1^2 + 1^2} = \sqrt2$. So the trail length is $$1 + 4\sqrt2 \approx \boxed{6.657}\ \text{miles}.$$

For the ellipse with semi-axes $a = \tfrac32$ (major) and $b = 1$ (minor), the medial axis is the segment of the major axis between the two centres of curvature at the major-axis vertices. The radius of curvature there is $b^2/a$, so each centre of curvature sits a distance $a - b^2/a = \tfrac{a^2 - b^2}{a}$ from the centre, and the trail runs between them, of length $$\frac{2(a^2 - b^2)}{a} = \frac{2\left(\tfrac94 - 1\right)}{\tfrac32} = \boxed{\tfrac53}\ \text{miles}.$$

The computation

For the ellipse, encode the definition directly: scan points $(t,0)$ along the major axis and find the largest $t$ whose nearest boundary point is off the vertex (so two symmetric nearest points exist); that half-length should be $(a^2-b^2)/a$.

import numpy as np
a, b = 1.5, 1.0
th = np.linspace(0, np.pi/2, 6000)
bx, by = a*np.cos(th), b*np.sin(th)                 # boundary, one quadrant
nearest = lambda t: th[np.argmin((bx - t)**2 + by**2)]
ts = np.linspace(0, a, 3000)
half = max(t for t in ts if nearest(t) > 1e-2)      # nearest point leaves the vertex
print(round(2*half, 4), 2*(a*a - b*b)/a)            # 1.6667  1.6667
print(1 + 4*np.sqrt(2))                             # rectangle: 6.657

The ellipse trail measures $\tfrac53 \approx 1.667$ miles and the rectangle trail $1 + 4\sqrt2 \approx 6.657$ miles, as boxed.

Riddler Classic

Define addition by nematodes: to add, pool the worms and wait a day; over that day the worms pair up and each pair produces one offspring with probability $\tfrac12$ (an odd worm sits out). Define a power as leaving the worms for that many days. What is the expected value of $(1+1)^4$? Extra credit: what does $(1+1)^N$ approach as $N$ grows?

The Riddler, FiveThirtyEight, August 7, 2020(original post)

Solution

Start with the two worms of $1+1$ and let one day pass per unit of the exponent. Each day, $n$ worms form $\lfloor n/2 \rfloor$ pairs, and each pair independently adds one worm with probability $\tfrac12$, so $n$ becomes $n + \mathrm{Binomial}\!\left(\lfloor n/2\rfloor, \tfrac12\right)$. Tracking the full distribution from $n = 2$ for four days gives $$\mathbb{E}\bigl[(1+1)^4\bigr] = \boxed{4.40625}.$$

The expected counts are $2.5,\ 3,\ 3.625,\ 4.40625, \ldots$ for $N = 1, 2, 3, 4$, and they fit an exact closed form. Were it not for the lonely odd worm, each day would multiply the expected population by $\tfrac54$ (every pair grows by half on average). The odd worm trims that growth by a constant, and the expected value works out to $$\mathbb{E}\bigl[(1+1)^N\bigr] = 2\left(\tfrac54\right)^{N-1} + \tfrac12,$$ so as $N$ grows it climbs like $\tfrac{8}{5}\left(\tfrac54\right)^{N}$, growing without bound at rate $\tfrac54$ per day.

The computation

Encode the day-by-day breeding exactly with rational arithmetic: evolve the distribution of worm counts and read off the expected value, checking it against the closed form.

from fractions import Fraction as Fr
from collections import defaultdict
from math import comb
def evolve(dist):                       # one day of pairing and breeding
    nd = defaultdict(Fr)
    for n, p in dist.items():
        pairs = n // 2
        for k in range(pairs + 1):
            nd[n + k] += p * Fr(comb(pairs, k), 2**pairs)
    return nd
dist = {2: Fr(1)}
for N in range(1, 5):
    dist = evolve(dist)
    E = sum(n*p for n, p in dist.items())
    print(N, float(E), E == 2*Fr(5, 4)**(N-1) + Fr(1, 2))
# N=4 -> 4.40625, closed form matches

The expected value of $(1+1)^4$ is $4.40625$, matching $2\left(\tfrac54\right)^{3} + \tfrac12$, as boxed.