How Long Is The Snail’s Slimy Trail?

Riddler Express

Six snails sit at the corners of a regular hexagon with side $10$ meters. Each snail crawls at the same speed directly toward its clockwise neighbour, which is itself moving. The six spiral inward to the centre. How long is each snail’s slime trail?

The Riddler, FiveThirtyEight, November 1, 2019(original post)

Solution

By symmetry the six snails always form a shrinking, rotating regular hexagon, so it is enough to watch one snail chasing its neighbour. The chaser always heads straight at its target, while the target moves off at a fixed angle. For a regular hexagon, the angle between a snail’s direction of travel and its neighbour’s direction of travel is the exterior turn, $360^\circ / 6 = 60^\circ$.

So the gap between a snail and the neighbour it chases shrinks at the rate the chaser approaches minus the rate the neighbour retreats along the line of sight. The chaser closes at its full speed; the neighbour’s velocity has a component $\cos 60^\circ = \tfrac12$ of its speed directed away. The net closing speed is therefore $1 - \tfrac12 = \tfrac12$ of the snail’s speed. A snail would crawl $10$ meters to reach a stationary target, but here the gap closes at half speed, so it must crawl twice as far: $$\boxed{20 \text{ meters}}.$$ In general, $n$ snails on a regular $n$-gon of side $a$ leave trails of length $a / (1 - \cos(2\pi/n))$; for $n = 6$, $a = 10$ that is $10 / (1 - \tfrac12) = 20$.

The computation

Encode the pursuit itself: place the six snails at the hexagon’s corners and, in small time steps, move each a little toward its clockwise neighbour, accumulating path length until they converge. The total length should approach $20$.

import numpy as np
def snail_trail(n=6, side=10.0, dt=1e-5):
    ang = np.array([2 * np.pi * i / n for i in range(n)])
    R = side / (2 * np.sin(np.pi / n))           # circumradius
    P = np.stack([R * np.cos(ang), R * np.sin(ang)], axis=1)
    length = 0.0
    while np.linalg.norm(P[0] - P[1]) > 1e-4:
        d = P[(np.arange(n) + 1) % n] - P         # toward clockwise neighbour
        d /= np.linalg.norm(d, axis=1, keepdims=True)
        P = P + dt * d; length += dt
    return length
print(round(snail_trail(), 3))                    # 20.0

Riddler Classic

A sultan will be shown $10$ marriage candidates one at a time in random order, ranked $1$ (best) to $10$ (worst). She must accept or reject each on sight; rejected candidates are gone. On seeing each, she knows only how it ranks among those seen so far. Playing optimally, what is the best (lowest) average rank of the candidate she ends up with?

The Riddler, FiveThirtyEight, November 1, 2019(original post)

Solution

This is the expected-rank version of the secretary problem. Work backwards. The key fact is that if the $i$-th candidate seen is the $r$-th best of those $i$, its expected rank among all $10$ is $r \cdot \tfrac{11}{i+1}$ (the $r$ known-better-or-equal positions scale up in proportion to how much of the field is still unseen).

Let $c_i$ be the expected final rank under optimal play from just before the $i$-th candidate. At the last candidate she must accept, and a random candidate averages rank $\tfrac{10+1}{2} = 5.5$, so $c_{10} = 5.5$. At earlier steps she accepts the current candidate if its accept-value $r \cdot \tfrac{11}{i+1}$ beats $c_{i+1}$, and otherwise waits: $$c_i = \frac1i \sum_{r=1}^{i} \min\!\left(r \cdot \frac{11}{i+1},\; c_{i+1}\right).$$ Iterating down to $c_1$ gives the answer, $$\boxed{\approx 2.558}.$$ So the sultan can expect a partner ranked about $2.56$ out of $10$: usually one of the very best, far better than the $5.5$ of accepting blindly. (At the ninth candidate she should accept anyone in the top four seen so far; the thresholds relax as the end nears.)

The computation

Encode the backward recursion directly: start from $c_{10} = 5.5$ and apply the accept-or-wait rule at each earlier position, averaging over the equally likely relative ranks.

def sultan(n=10):
    c = (n + 1) / 2                               # c_n: forced to accept the last
    for i in range(n - 1, 0, -1):
        c = sum(min(r * (n + 1) / (i + 1), c) for r in range(1, i + 1)) / i
    return c
print(round(sultan(), 3))                         # 2.558

The recursion returns $2.558$, the best expected rank the sultan can guarantee.