How Many Soldiers Do You Need To Beat The Night King?

Riddler Express

Navigate a nine-by-nine grid of colored lines three times, once as blue, once as yellow, once as red, traversing only lines containing your color. The maze graphic is supplied in the original post.

The Riddler, FiveThirtyEight, May 17, 2019(original post)

Status

This puzzle’s statement is the maze graphic itself: a nine-by-nine grid in which each edge has a colour drawn from blue, yellow, red, green, purple, orange, white (passable by every colour), or black (passable by none), with the start and finish vertices marked on the image. The corpus does not preserve the maze as machine-readable data, and the puzzle is unsolvable without the per-edge colour assignment.

The official solution shipped the route as another image. With the input image and the route image both lost to text-only archives, this puzzle is deferred for the same reason as earlier image-only Riddlers, the gerrymander grid of October $2016$ and the map-colouring of November $2016$.

Riddler Classic

The Night King raises every fallen living soldier into the army of the dead. Each army lines up single file. One soldier steps forward from each side and they duel; each side wins with probability $\tfrac{1}{2}$. If the living wins, the dead soldier is gone forever and the living goes to the back of his line. If the dead wins, the dead goes to the back of his line and the (formerly) living soldier joins him there. The battle continues until one army is empty. What starting sizes $L$ (living) and $D$ (dead) give each army a $50$–$50$ chance of winning?

The Riddler, FiveThirtyEight, May 17, 2019(original post)

Solution

Let $p(L, D)$ be the probability that the living army wins, starting from $L$ living and $D$ dead. Boundary cases: $$p(L, 0) \;=\; 1 \ \text{for} \ L \ge 1, \qquad p(0, D) \;=\; 0 \ \text{for} \ D \ge 1.$$ At any interior state $(L, D)$ the next duel resolves with probability $\tfrac{1}{2}$ each way, giving the recursion $$p(L, D) \;=\; \tfrac{1}{2}\, p(L,\, D - 1) \;+\; \tfrac{1}{2}\, p(L - 1,\, D + 1).$$ The puzzle asks for $(L, D)$ with $p(L, D) = \tfrac{1}{2}$.

Random-walk view. Index duels by $n = 1, 2, \ldots$ and let $X_{n} \in \{+1, -1\}$ be the outcome of the $n$-th duel from the living’s perspective: $+1$ if the living wins, $-1$ if the dead wins. The $X_{n}$ are i.i.d. fair coin flips. After $W$ wins and $\ell$ losses by the living, $$\text{dead remaining} \;=\; D - W + \ell, \qquad \text{living remaining} \;=\; L - \ell.$$ The living army wins iff the dead reach $0$ before the living do, i.e., iff $$W - \ell \;=\; D \ \text{occurs before} \ \ell \;=\; L.$$ Equivalently, $S_{n} \equiv \sum_{k \le n} X_{k}$ hits $+D$ before the number of $-1$ steps reaches $L$.

Why the scaling is $L \approx D^{2}$. Each duel costs the dead exactly one soldier in expectation: with probability $\tfrac{1}{2}$ the dead lose one, and with probability $\tfrac{1}{2}$ they gain one, so the dead random walk has zero drift and standard deviation $1$ per step. The dead army’s count is a fair random walk that absorbs at $0$ from the start point $D$. By the gambler’s-ruin result on a fair walk, the expected number of duels until the dead count touches $0$ is infinite, but the median is on the order of $D^{2}$.

The living army, in contrast, loses exactly one soldier with probability $\tfrac{1}{2}$ per duel and is unchanged otherwise, so its count is a one-sided walk with drift $-\tfrac{1}{2}$. After $n$ duels the living is expected to have lost $n/2$ soldiers. For the living to outlast the dead’s exhaustion (median time $\sim D^{2}$), the living needs $L \gtrsim D^{2}/2$. The factor in front turns out to be close to $1$ for small $D$ and grows slowly: numerical solution of the recursion gives the half-chance frontier in the table below.

Half-chance frontier (smallest $L$ with $p(L, D) \ge \tfrac{1}{2}$). $$\begin{aligned} D = 1:&\ L = 1,\ p = 0.5000; \quad D = 2:\ L = 4,\ p = 0.5078; \\ D = 3:&\ L = 9,\ p = 0.5034; \quad D = 4:\ L = 17,\ p = 0.5114; \\ D = 5:&\ L = 26,\ p = 0.5044; \quad D = 6:\ L = 38,\ p = 0.5052; \\ D = 8:&\ L = 67,\ p = 0.5006; \quad D = 10:\ L = 106,\ p = 0.5012; \\ D = 15:&\ L = 241,\ p = 0.5007; \quad D = 20:\ L = 431,\ p = 0.5004. \end{aligned}$$ The ratio $L/D^{2}$ rises gently from $1.00$ at $D = 1, 2, 3$ to about $1.08$ at $D = 20$, consistent with the asymptotic $L \sim D^{2}$ derived above.

The headline number from the official is $L = 100$ for $D = 10$ as a rule-of-thumb (square scaling), but the exact frontier rounds slightly above $L = D^{2}$ for $D \ge 4$. The discrepancy comes from the asymmetry of the duel: each living loss adds to the dead, so the dead’s random walk drifts upward whenever the living lose, and the living need a bit more than $D^{2}$ to compensate.

The computation

Encode the duel directly: track $(L, D)$ pair, draw fair coin flips, and record who wins. The empirical win rate at the boxed pairs must match $\tfrac{1}{2}$. Cross-check against the DP that solves the recursion exactly.

1. Implement the recursion with memoisation. The state space at $(L_{0}, D_{0})$ is bounded by total budget $2 L_{0} + D_{0}$ duels, which the DP iterates in ascending budget order.

2. For each $D$ from $1$ to $20$, binary-search the smallest $L$ with $p(L, D) \ge \tfrac{1}{2}$.

3. Monte Carlo the duel sequence at a few boxed pairs.

import random

def solve(target_D, target_L):
    Dmax = target_D + target_L + 2
    Lmax = target_L + 2
    p = [[0.0] * (Dmax + 1) for _ in range(Lmax + 1)]
    for L in range(Lmax + 1):
        p[L][0] = 1.0 if L >= 1 else 0.0
    for tot in range(1, 2 * Lmax + Dmax + 1):
        for L in range(0, Lmax + 1):
            D = tot - 2 * L
            if D <= 0 or D > Dmax:
                continue
            if L == 0:
                p[0][D] = 0.0
                continue
            nxt = p[L - 1][D + 1] if D + 1 <= Dmax else 0.0
            p[L][D] = 0.5 * p[L][D - 1] + 0.5 * nxt
    return p[target_L][target_D]

def smallest_L(D, hi=2000):
    lo = 1
    while lo < hi:
        mid = (lo + hi) // 2
        if solve(D, mid) >= 0.5:
            hi = mid
        else:
            lo = mid + 1
    return lo

def simulate(L, D, trials):
    wins = 0
    for _ in range(trials):
        Ll, Dd = L, D
        while Ll > 0 and Dd > 0:
            if random.random() < 0.5:
                Dd -= 1                          # living wins duel
            else:
                Ll -= 1
                Dd += 1                          # dead wins duel
        if Dd == 0:
            wins += 1
    return wins / trials

random.seed(2019)
for D in [1, 2, 3, 4, 5, 6, 8, 10, 15, 20]:
    L = smallest_L(D)
    p_exact = solve(D, L)
    p_sim = simulate(L, D, 20_000) if D <= 10 else float("nan")
    print(f"D={D:>3}: L={L:>4}  p_exact={p_exact:.4f}  "
          f"L/D^2={L/D**2:.3f}  p_sim={p_sim:.4f}")

The script prints the half-chance frontier $$\begin{aligned} (D, L) \;=\;& (1, 1),\ (2, 4),\ (3, 9),\ (4, 17),\ (5, 26), \\ & (6, 38),\ (8, 67),\ (10, 106),\ (15, 241),\ (20, 431), \end{aligned}$$ matching the boxed table, with the empirical Monte Carlo agreeing to within $\pm 0.005$ at each pair where simulation is run.