Can You Stay In Your Lane?

Riddler Express

A pool has five lanes, and swimmers may not use adjacent lanes. Swimmers arrive one at a time and each picks uniformly at random among the lanes still available (empty and not adjacent to an occupied lane), until none remain. What is the expected number of swimmers? Extra credit: with $N$ lanes?

The Riddler, FiveThirtyEight, July 3, 2020(original post)

Solution

When the first swimmer takes lane $k$, lane $k$ and its neighbours $k\pm1$ are removed, splitting the remaining lanes into two independent blocks: lanes $1,\ldots,k-2$ on the left and $k+2,\ldots,N$ on the right. Each block then fills by the same rule, independently, so the expected counts add. Writing $E_N$ for the expected number of swimmers among $N$ lanes in a row, $$E_N = 1 + \frac1N \sum_{k=1}^{N}\bigl(E_{k-2} + E_{N-k-1}\bigr),$$ with $E_0 = 0$, $E_1 = 1$ (and negative indices zero). This is exactly the “random sequential adsorption” recurrence. Evaluating it for five lanes, $$E_5 = \boxed{\tfrac{37}{15} \approx 2.467}.$$ For the extra credit, the fraction of lanes filled, $E_N/N$, settles between the best case ($\tfrac12$, alternating lanes) and the worst ($\tfrac13$, two gaps each), approaching the classic Rényi parking constant $$\lim_{N\to\infty}\frac{E_N}{N} = \frac{1 - e^{-2}}{2} \approx \boxed{0.4323}.$$

The computation

Encode the recurrence (which captures the actual lane-by-lane filling, since the two sides fill independently) and read off $E_5$; then watch $E_N/N$ approach the limiting density.

from fractions import Fraction as F
import math
def table(N, zero, one):                # iterative fill of E[0..N]
    E = [zero] * (N + 1)
    if N >= 1: E[1] = one
    for n in range(2, N + 1):
        E[n] = 1 + sum(E[max(k - 2, 0)] + E[max(n - k - 1, 0)]
                       for k in range(1, n + 1)) / n
    return E
print("E(5) =", table(5, F(0), F(1))[5])                # 37/15 (exact)
E = table(500, 0.0, 1.0)                                # float for the density
print("density E(500)/500 =", round(E[500] / 500, 4),
      " limit =", round((1 - math.e**-2) / 2, 4))
# E(5) = 37/15
# density E(500)/500 = 0.4329  limit = 0.4323

Riddler Classic

The $50$ stars on the flag form a pattern that works because $50$ is twice a square. A proposed $51$-star design uses a centre star ringed by concentric pentagons, which works because $51$ is a centered pentagonal number. So $N = 50$ has the property that $N$ is twice a square and $N+1$ is a centered pentagonal number. What is the next integer $N$ with both properties?

The Riddler, FiveThirtyEight, July 3, 2020(original post)

Solution

“Twice a square” means $N = 2x^2$. A centered pentagonal number is $1 + 5\cdot\tfrac{y(y+1)}{2}$ (a central dot plus rings of $5, 10, 15, \ldots$), so requiring $N + 1$ to be one gives $2x^2 = \tfrac{5y(y+1)}{2}$, that is $$4x^2 = 5\,y(y+1).$$ The pair $(x, y) = (5, 4)$ gives $N = 50$. This is a Pell-type relation, and its solutions grow fast; the next one is $(x, y) = (90, 80)$, giving $$N = 2\cdot 90^2 = \boxed{16200},$$ with $N + 1 = 16201$ the $81$st centered pentagonal number. (After that the next is $N = 5{,}216{,}450$.)

The computation

Encode both properties directly: sweep $x$, form $N = 2x^2$, and test whether $N+1$ is centered pentagonal (a value $1 + 5\,m(m{-}1)/2$). Report the values past $50$.

cps = {(5 * m * m - 5 * m + 2) // 2 for m in range(1, 100000)}   # centered pentagonals
out = []
x = 1
while len(out) < 3:
    N = 2 * x * x
    if N + 1 in cps: out.append(N)
    x += 1
print(out)            # [50, 16200, 5216450]