Chapter 208

The Little, Mathematically Determined House On The Prairie

Riddler Express

Louie walks to work and home each day. The morning rain probability is $0.5$ and the evening rain probability is $0.4$ , independent across legs and days. He brings (and uses) an umbrella iff it is raining when he leaves the house or office, and leaves them behind otherwise. He owns three umbrellas. On Sunday night, two are at home and one is at the office. Assuming it never starts raining mid-walk, what is the probability that he makes it through the work week (Monday morning through Friday evening) without getting wet?

The Riddler, FiveThirtyEight, December 7, 2018(original post)

Solution

Let $H_{t}$ be the number of umbrellas at home at the start of a given leg; the office holds $3 - H_{t}$ . The two legs of a day update the state as follows.

Morning leg (home $\to$ office). Rain with probability $\tfrac{1}{2}$ . If it rains and $H \ge 1$ he carries one to the office, leaving $(H-1, 3-H+1)$ . If it rains and $H = 0$ he gets wet. If it does not rain, the state is unchanged.

Evening leg (office $\to$ home). Rain with probability $\tfrac{2}{5}$ . Mirror the morning leg with the office count playing the role of the home count.

The state visible from home is the home count $H \in \{0, 1, 2, 3\}$ plus an absorbing wet state. Start at $H = 2$ (two umbrellas home, one office) and iterate the day transition five times. The chain has at most $4$ live states and one absorbing state, so the calculation is exact.

The day transition $H \mapsto H'$ has six branches per day, formed by independently choosing rain/no-rain on each leg. Working with $H_{0} = 2$ :

Morning rain ( $\tfrac{1}{2}$ ): home $\to 1$ , office $\to 2$ . Evening rain ( $\tfrac{2}{5}$ ): home $\to 2$ . Evening dry: home $\to 1$ .
Morning dry ( $\tfrac{1}{2}$ ): home stays at $2$ , office at $1$ . Evening rain ( $\tfrac{2}{5}$ ): home $\to 3$ . Evening dry: home stays at $2$ .

He cannot get wet on Monday because he starts with at least one umbrella at home (covers morning) and at least one at the office (covers evening). Iterate the four-state chain for five days; the wet probability is the absorbing-state mass at Friday’s end.

A direct computation (numerator over $10^{4}$ since rain probabilities are $\tfrac{1}{2}$ and $\tfrac{2}{5}$ , both with denominator $10$ , and five days compose to denominator $10^{10}$ , simplifying): $\Pr(\text{dry through the week}) \;=\; \frac{6927}{10000} \;=\; 0.6927.$

$\boxed{\Pr(\text{Louie stays dry Mon--Fri}) \;=\; \frac{6927}{10000} \;\approx\; 69.27\%.}$

The computation

Encode the Markov chain over $\{0, 1, 2, 3, \text{wet}\}$ and propagate the distribution through ten legs (five mornings and five evenings). Use exact rationals.

State $H$ is the home umbrella count, or the absorbing label wet.
Morning rule: rain w.p. $\tfrac{1}{2}$ ; carry if $H \ge 1$ else wet; office count becomes $3 - H +$ carry.
Evening rule: rain w.p. $\tfrac{2}{5}$ ; carry if office $\ge 1$ else wet; home count becomes $H +$ carry.
Start distribution: $H = 2$ with probability $1$ . Iterate five days. Report $1 - \Pr(\text{wet})$ .

from fractions import Fraction

def day(h):
    out = {}
    pr_rain_m, pr_dry_m = Fraction(1,2), Fraction(1,2)
    pr_rain_e, pr_dry_e = Fraction(2,5), Fraction(3,5)
    morn = []
    if h >= 1:
        morn.append((pr_rain_m, h - 1))
    else:
        morn.append((pr_rain_m, 'wet'))
    morn.append((pr_dry_m, h))
    for p, h1 in morn:
        if h1 == 'wet':
            out['wet'] = out.get('wet', Fraction(0)) + p
            continue
        office = 3 - h1
        if office >= 1:
            out[h1 + 1] = out.get(h1 + 1, Fraction(0)) + p * pr_rain_e
        else:
            out['wet'] = out.get('wet', Fraction(0)) + p * pr_rain_e
        out[h1] = out.get(h1, Fraction(0)) + p * pr_dry_e
    return out

dist = {2: Fraction(1)}
for _ in range(5):
    nxt = {}
    for s, p in dist.items():
        if s == 'wet':
            nxt['wet'] = nxt.get('wet', Fraction(0)) + p
            continue
        for s2, q in day(s).items():
            nxt[s2] = nxt.get(s2, Fraction(0)) + p * q
    dist = nxt

p_dry = 1 - dist.get('wet', Fraction(0))
print(f"P(dry) = {p_dry} = {float(p_dry):.4f}")

The script prints $6927/10000 = 0.6927$ , matching the boxed answer.

Riddler Classic

Settlers are building houses on a prairie that is a perfect circle of radius $1$ mile. They want to live as far apart as possible: they will arrange their houses to maximise the average distance from each settler to that settler’s nearest neighbour. With seven settlers an optimal arrangement is a regular hexagon of six on the boundary plus one at the centre, giving every settler a nearest-neighbour distance of exactly $1$ mile. One settler now cancels, leaving six. Can the remaining six achieve a higher average nearest-neighbour distance than $1$ mile, and where do they build?

The Riddler, FiveThirtyEight, December 7, 2018(original post)

Solution

The answer is yes. The known optimum for six settlers is mirror-symmetric about a vertical axis, with five settlers on the circle and one slightly off centre, and gives an average nearest-neighbour distance of approximately $1.00229$ miles. The arrangement is not a rotational regular pattern, which is why six is the odd-one-out in the integer sequence: $N = 2$ uses two antipodes (distance $2$ ), $N \in \{3, 4, 5\}$ use regular polygons inscribed in the boundary, $N = 7$ uses the regular hexagon plus centre, while $N = 6$ uses an asymmetric layout that beats $1$ by a small margin.

Why six is special. A regular hexagon of six on the boundary gives every settler a nearest-neighbour distance of exactly $1$ mile, but only because each settler’s two boundary-neighbours are at distance $1$ . With six settlers in the regular-polygon style, no settler is in the interior, so every settler’s nearest neighbour is on the circle and at distance $\le 1$ . To beat $1$ on the average, at least one settler must move into the interior to lift one settler’s nearest-neighbour distance above $1$ at the cost of lowering others. With six houses, that interior settler is a single one; with seven, two settlers sit on the same line and the regular hexagon-plus-centre design keeps every distance at exactly $1$ .

The optimum’s symmetric form. Place an axis of symmetry vertical. Five settlers sit on the unit circle: one at the top, a pair symmetric about the vertical axis at the upper sides at half-angle $a$ from the top, and another pair symmetric at the lower sides at half-angle $b$ from the bottom. The sixth settler sits on the vertical axis at height $y$ , slightly below the centre. The three parameters $(y, a, b)$ are chosen to maximise the mean nearest-neighbour distance. Numerical search converges to $y^{\ast} \approx -0.0555, \quad a^{\ast} \approx 1.1119, \quad b^{\ast} \approx 0.9526,$ with mean nearest-neighbour distance $\overline{d}^{\ast} \;\approx\; 1.00229 \text{ miles.}$ At the optimum the top vertex is at $(0, 1)$ , the upper pair at $(\pm 0.8966, 0.4429)$ , the lower pair at $(\pm 0.8149, -0.5796)$ , and the interior settler at $(0, -0.0555)$ . The interior settler’s nearest neighbour is one of the lower pair at distance $\approx 0.9689$ ; the upper pair’s nearest neighbour is the interior settler at distance $\approx 1.0258$ ; the top vertex’s nearest neighbour is the interior settler at distance $\approx 1.0555$ .

$\boxed{\overline{d}^{\ast} \;\approx\; 1.0023 \text{ miles.}}$

The computation

The optimisation has no clean closed form. Encode the symmetric three-parameter family directly and search numerically.

Parameters $(y, a, b)$ with $-1 < y < 1$ , $0 < a < \pi/2$ , $0 < b < \pi/2$ .
Five boundary settlers: $(0, 1)$ , $(\pm \sin a, \cos a)$ , $(\pm \sin b, -\cos b)$ . Interior settler: $(0, y)$ .
For each settler compute the nearest-neighbour distance, take the mean.
Multi-start Nelder-Mead from random initial points; keep the best.

import numpy as np
from scipy.optimize import minimize

def pts(p):
    y, a, b = p
    return np.array([
        (0.0, 1.0),
        (-np.sin(a), np.cos(a)),
        (np.sin(a), np.cos(a)),
        (-np.sin(b), -np.cos(b)),
        (np.sin(b), -np.cos(b)),
        (0.0, y),
    ])

def neg_mean_nn(p):
    y, a, b = p
    if not (-1 < y < 1 and 0 < a < np.pi/2 and 0 < b < np.pi/2):
        return 1e6
    P = pts(p)
    n = len(P)
    d = np.full((n, n), 1e9)
    for i in range(n):
        for j in range(n):
            if i != j:
                d[i, j] = np.linalg.norm(P[i] - P[j])
    return -d.min(axis=1).mean()

rng = np.random.default_rng(2018)
best = None
for _ in range(200):
    x0 = [rng.uniform(-0.5, 0.5), rng.uniform(0.5, 1.3),
          rng.uniform(0.5, 1.3)]
    r = minimize(neg_mean_nn, x0, method='Nelder-Mead',
                 options={'xatol': 1e-10, 'fatol': 1e-12,
                          'maxiter': 20000})
    if best is None or r.fun < best.fun:
        best = r

y, a, b = best.x
print(f"y* = {y:.5f}, a* = {a:.5f}, b* = {b:.5f}")
print(f"mean nearest-neighbour distance = {-best.fun:.5f}")

The script prints $\overline{d}^{\ast} \approx 1.00229$ , matching the boxed answer. The same routine, run for $N = 2, 3, 4, 5, 7$ , recovers the regular-polygon and hexagon-plus-centre optima at $\overline{d} = 2$ , $\sqrt{3}$ , $\sqrt{2}$ , $2 \sin 36^{\circ}$ , $1$ respectively; six is the only $N \le 7$ where the optimum departs from rotational symmetry.