Three Daughters And One Hundred Boxes

Riddler Express

A farmer wants to divide his $1 \times 1$ square farm into three pieces of equal area using fencing. What is the shortest total length of fence he needs?

The Riddler, FiveThirtyEight, October 6, 2017(original post)

Solution

The obvious answer, two parallel cuts of length $1$, uses $2$ miles of fence. A T-shape with one full cut and a short perpendicular spur uses $1 + \tfrac23 \approx 1.67$. A Y-shape with two straight diagonals does slightly better, around $1.635$. But the optimum is none of these: it uses three circular arcs meeting at a Steiner point at $120^{\circ}$ to one another, and totals about $1.6233$ miles.

Why arcs, and why $120^{\circ}$. The classical Steiner condition for shortest networks says that three boundary curves meeting at a free interior point must do so at equal $120^{\circ}$ angles. Otherwise the local geometry permits a perturbation that strictly shortens the network. The same condition forces each curve to meet the square’s boundary at a right angle (or else a tangential slide along the boundary would shorten the curve). The third condition is that each curve has constant curvature, that is, each is a circular arc (or a line segment, the zero-curvature special case): along an arc of varying curvature one could swap a short piece for one of constant curvature with the same endpoints and strictly less length under the area constraint.

These three conditions, taken together with the demand that the three regions have area $\tfrac13$ each, pin down a one-parameter family of candidate networks. The symmetric solution, with the Steiner point on the vertical axis of symmetry and two mirror-image arcs running to the two side edges plus a straight stem to the bottom edge, is the global optimum (the asymmetric variants are dominated).

Setting it up. Place the unit square with corners at $(0, 0)$, $(1, 0)$, $(1, 1)$, $(0, 1)$. By symmetry put the Steiner point $S = (\tfrac12, z)$ for some $z > 0$, drop a straight stem from $S$ to the midpoint of the bottom edge, and have one arc leave $S$ at $30^{\circ}$ above horizontal and end perpendicular to the right edge at $(1, y_E)$, with the mirror arc going left.

Pinning down the arc. The tangent at $S$ points in direction $(\cos 30^{\circ}, \sin 30^{\circ}) = (\tfrac{\sqrt{3}}{2}, \tfrac12)$. The centre of the arc is perpendicular to the tangent on the concave side, at the constant distance equal to the radius $R$. For the arc to also meet the right edge perpendicular to that edge, the centre must lie on the right edge itself. These two requirements fix $$R = 1, \quad C = (1,\; z - \tfrac{\sqrt{3}}{2}), \quad y_E = z + 1 - \tfrac{\sqrt{3}}{2}.$$ The arc sweeps from $S$ at central angle $\tfrac{2\pi}{3}$ to its endpoint at $\tfrac{\pi}{2}$, so its arc length is $R \cdot (\tfrac{2\pi}{3} - \tfrac{\pi}{2}) = \tfrac{\pi}{6}$. Two arcs and a stem give total length $z + \tfrac{\pi}{3}$.

Pinning down the stem. The area constraint demands each region equals $\tfrac13$. Take the right-bottom region (bounded counter-clockwise by the bottom edge from $(\tfrac12, 0)$ to $(1, 0)$, the right edge from $(1, 0)$ to $(1, y_E)$, the right arc back to $S$, and the stem down to $(\tfrac12, 0)$). Applying the shoelace formula and integrating along the arc gives, with $C = (1,\; z - \tfrac{\sqrt{3}}{2})$, $$\begin{aligned} 2A &= y_E - \tfrac{z}{2} + \int_{\pi/2}^{2\pi/3}\!\!\big[1 + \cos\phi + (z - \tfrac{\sqrt{3}}{2})\sin\phi\big]\,d\phi\\ &= y_E - \tfrac{z}{2} + \tfrac{\pi}{6} + (\sin\tfrac{2\pi}{3} - 1) - (z - \tfrac{\sqrt{3}}{2})(\cos\tfrac{2\pi}{3} - 0). \end{aligned}$$ Setting $A = \tfrac13$ and solving for $z$ numerically gives $z \approx 0.5761$. Adding the two arc lengths, $$L = z + \tfrac{\pi}{3} \approx 0.5761 + 1.0472 \approx \boxed{1.6233 \text{ miles.}}$$ The straight-Y configuration is only about a thousandth of a mile longer than this; the curvature wins by a thin margin but is the true optimum.

The computation

Encode the geometry: compute the area of the right-bottom region as a function of the stem length $z$, then root-find for $A(z) = \tfrac13$. Sum the resulting stem plus two arcs of length $\tfrac{\pi}{6}$.

1. Define the arc’s centre $C(z)$ and endpoint $y_E(z)$ from the geometry above.

2. Compute the right-bottom area $A(z)$ by Green’s theorem along the closed boundary.

3. Root-find for $A(z) = \tfrac13$.

4. Report $L = z + \tfrac{\pi}{3}$.

import numpy as np
from scipy.optimize import brentq

def area_right_bot(z):
    y_E = z + 1 - np.sqrt(3) / 2
    cy = z - np.sqrt(3) / 2
    a, b = np.pi / 2, 2 * np.pi / 3
    arc = ((b - a)
           + (np.sin(b) - np.sin(a))
           + cy * (np.cos(a) - np.cos(b)))
    return 0.5 * (y_E + arc - 0.5 * z)

z = brentq(lambda z: area_right_bot(z) - 1 / 3, 0.3, 0.8)
print(round(z, 4))                                   # 0.5761
print(round(z + np.pi / 3, 4))                       # 1.6233

Riddler Classic

You and three friends are on a game show. Four boxes hold your four names, one per box. Each player enters the room alone, opens up to two boxes, and looks for their own name. Everyone enters exactly once. You win if all four find their own name. Find a strategy that beats the naive $1/16$. Extra credit: $100$ players, $100$ boxes, $50$ openings each.

The Riddler, FiveThirtyEight, October 6, 2017(original post)

Solution

The trick is to give each player a linked search, in which finding her name on any player’s tour is automatic, by following the permutation’s cycles. The strategy and its analysis are due to Anna Gál and Peter Bro Miltersen.

The strategy. Number the players $1, 2, 3, 4$ and the boxes $1, 2, 3, 4$. Player $i$ first opens box $i$. If she finds her own name she is done. If she finds the name of player $j$, she next opens box $j$, then $k$ (whichever name was in box $j$), and so on, up to her opening limit of two.

The contents of the boxes define a permutation $\sigma$ on $\{1, 2, 3, 4\}$: box $i$ contains the name of player $\sigma(i)$. Decompose $\sigma$ into disjoint cycles. Player $i$’s tour walks the cycle containing $i$: she sees $\sigma(i), \sigma^2(i), \sigma^3(i), \ldots$, and finds her own name on the step that closes the cycle. So she wins iff her cycle has length at most $2$ (the opening limit).

Every player wins iff every cycle has length at most $2$. Out of the $4! = 24$ permutations on four letters, the ones with no cycle longer than $2$ are those whose cycle type is $(1, 1, 1, 1)$, $(2, 1, 1)$, or $(2, 2)$. There is $1$ of the first type (the identity), $\binom{4}{2} = 6$ of the second (one transposition, two fixed points), and $\tfrac{1}{2}\binom{4}{2} = 3$ of the third (two disjoint transpositions). Total $10$. $$\boxed{\,\Pr(\text{team wins}) = \tfrac{10}{24} \approx 41.7\%.\,}$$ Comfortably more than $1/16 \approx 6.25\%$.

Extra credit. With $100$ players, $100$ boxes, and $50$ openings each, the same cycle strategy applies. The team wins iff the random permutation $\sigma$ on $\{1, \ldots, 100\}$ has no cycle of length greater than $50$. At most one such long cycle can exist, since two cycles of length more than $50$ would need more than $100$ elements between them.

For each $k > 50$, count the permutations with a cycle of length exactly $k$. Choose which $k$ of the $100$ elements form that cycle ($\binom{100}{k}$ ways), arrange them into a cycle ($(k-1)!$ ways for a directed cycle on $k$ vertices), and permute the remaining $100 - k$ elements freely ($(100 - k)!$ ways). The total is $$\binom{100}{k}(k - 1)!\,(100 - k)! = \frac{100!}{k},$$ so the fraction of permutations with such a cycle is $1/k$. These events are disjoint for different $k > 50$ (only one long cycle can exist), so $$\Pr(\text{some cycle has length} > 50) = \sum_{k=51}^{100} \frac{1}{k} = H_{100} - H_{50},$$ where $H_n = 1 + \tfrac12 + \cdots + \tfrac1n$ is the $n$-th harmonic number. $$\Pr(\text{team wins}) = 1 - (H_{100} - H_{50}) \approx 1 - 0.6882 = 0.3118.$$ $$\boxed{\,\Pr(\text{team wins with } 100 \text{ boxes}) \approx 31.18\%.\,}$$ As $n \to \infty$ with the opening limit fixed at $n/2$, the win probability tends to $1 - \ln 2 \approx 0.3069$, a constant independent of the number of prisoners. This is the celebrated $100$-prisoners theorem.

The computation

For $n = 4$, enumerate all $24$ permutations and count those whose longest cycle is at most $2$. For $n = 100$, simulate random permutations and check the same condition. Both should reproduce the boxed values.

1. For $n = 4$: iterate over all permutations of $\{1, 2, 3, 4\}$; for each, compute its cycle structure; count those with maximum cycle length $\leq 2$.

2. For $n = 100$: generate random permutations, find the longest cycle of each, count those with length $\leq 50$.

from itertools import permutations
import random

def max_cycle_len(p):
    seen = [False] * len(p)
    best = 0
    for i in range(len(p)):
        if seen[i]: continue
        j, L = i, 0
        while not seen[j]:
            seen[j] = True
            j = p[j]
            L += 1
        if L > best: best = L
    return best

n4 = sum(1 for p in permutations(range(4)) if max_cycle_len(p) <= 2)
print(n4, round(n4 / 24, 4))                         # 10  0.4167

rng = random.Random(0)
N = 200_000
wins = 0
for _ in range(N):
    p = list(range(100)); rng.shuffle(p)
    if max_cycle_len(p) <= 50: wins += 1
print(round(wins / N, 4))                            # ~0.3118

The four-box exhaustive count gives $10/24$ exactly; the $100$-box Monte Carlo lands within sampling error of $0.3118$, matching both the boxed answer and the $1 - \ln 2$ limit.