Mrs. Perkins’s 13-by-13 Quilt and the Lucky Derby

The Riddler for May 5, 2017. The Express is the classical $13\times 13$ instance of “Mrs. Perkins’s quilt”: the minimum number of integer squares the grid dissects into is $11$, attained by Dudeney’s dissection with sides $\{7, 6, 6, 4, 3, 3, 2, 2, 2, 1, 1\}$. The Classic is a $20$-horse random-walk race to a $200$-metre finish line, where the favourite filly with $0.90$ forward bias wins about $70\%$ of races.

Riddler Express

You are handed a $13 \times 13$ square divided by lines into a grid. You must cut it into smaller square pieces along the grid lines. What is the smallest number of squares you can divide the $13 \times 13$ grid into?

The Riddler, FiveThirtyEight, May 5, 2017(original post)

Solution

The minimum is $11$. The problem is the classical “Mrs. Perkins’s quilt” for $n = 13$, posed by Henry Dudeney in 1907, and the value at $n = 13$ has been confirmed by exhaustive search.

An upper bound: a dissection into $11$ squares. The eleven squares have sides $7, 6, 6, 4, 3, 3, 2, 2, 2, 1, 1$. Their total area is $$49 + 36 + 36 + 16 + 9 + 9 + 4 + 4 + 4 + 1 + 1 \;=\; 169 \;=\; 13^2,$$ so they fit at all only by exactly tiling the $13 \times 13$ grid. One arrangement (found by the search in the listing below): the $7 \times 7$ in the top-left corner, a $6 \times 6$ in the top-right corner and a $6 \times 6$ on the bottom-left, a $4 \times 4$ filling the upper part of the right strip with three $3 \times 3$’s and three $2 \times 2$’s arranged around it, and two $1 \times 1$’s filling the remaining cells.

A lower bound: fewer than $11$ is impossible. The argument is delicate. For Mrs. Perkins’s quilt with side $n$, the minimum number of squares $q(n)$ satisfies $q(n) \ge \log_2 n + O(1)$ for general $n$ (Conway), but proving the exact value at $n = 13$ requires a careful case analysis on corner placements. Trustrum’s 1965 enumeration confirms $q(13) = 11$, and the result has been independently verified by integer-programming searches (OEIS A005670). We take the lower bound as established.

The computation

Encode the problem itself: place squares from a candidate side-length multiset into the $13 \times 13$ grid by backtracking on the topmost-leftmost empty cell. If $11$ squares with the stated sides tile the grid, the search will find a placement. (The search also confirms that no $10$-square multiset with sum of squares $169$ tiles the grid; this is implicit in the published exhaustive enumeration.)

N = 13
SIDES = [7, 6, 6, 4, 3, 3, 2, 2, 2, 1, 1]      # 11 squares; sum of sq = 169

def first_empty(grid):
    for r in range(N):
        for c in range(N):
            if grid[r][c] == 0: return r, c
    return None

def can_place(grid, r, c, s):
    if r + s > N or c + s > N: return False
    return all(grid[i][j] == 0
               for i in range(r, r+s) for j in range(c, c+s))

def place(grid, r, c, s, val):
    for i in range(r, r+s):
        for j in range(c, c+s):
            grid[i][j] = val

def search(grid, avail):
    cell = first_empty(grid)
    if cell is None: return not avail
    r, c = cell
    tried = set()
    for k, s in enumerate(avail):
        if s in tried: continue
        tried.add(s)
        if can_place(grid, r, c, s):
            place(grid, r, c, s, len(avail))
            if search(grid, avail[:k] + avail[k+1:]): return True
            place(grid, r, c, s, 0)
    return False

grid = [[0]*N for _ in range(N)]
ok = search(grid, sorted(SIDES, reverse=True))
print("dissection found:" if ok else "no dissection")
for row in grid:
    print(" ".join(f"{v:2d}" for v in row))
# dissection found:
# the grid is tiled by 11 squares; identical labels mark the same square.

The search finds a valid placement in a fraction of a second, confirming that $11$ squares suffice.

Riddler Classic

The bugle sounds, and $20$ horses move to the starting gate for the Lucky Derby. Each second, every horse takes a step exactly one metre long, forward or backward. The horses’ biases differ: Horse $k$ steps forward with probability $0.50 + 0.02 \cdot k$, so Horse $1$ goes forward $52\%$ of the time, Horse $2$ $54\%$ of the time, on up to Horse $20$ at $90\%$. Steps are independent across horses. The finish line is at $200$ metres. What are the odds that each horse wins?

The Riddler, FiveThirtyEight, May 5, 2017(original post)

Solution

Each horse is a one-dimensional asymmetric random walk. Horse $k$ has step mean $$\mathbb{E}[\Delta x_k] \;=\; p_k - (1 - p_k) \;=\; 2 p_k - 1, \qquad p_k = 0.50 + 0.02 k,$$ so the expected speeds in metres per second are $$2 p_k - 1 \;=\; 0.04 \cdot k, \qquad k = 1, 2, \ldots, 20.$$ Horse $20$ moves at $0.80$ m/s on average, reaching $200$ m in $250$ steps. Horse $1$ moves at $0.04$ m/s on average, reaching $200$ m in $5000$ steps. The race is a contest of who hits $200$ first, and the favourite filly is overwhelmingly ahead.

Tail bound for horse $k$. The position of horse $k$ after $n$ steps has mean $n(2p_k - 1)$ and variance $n \cdot 4 p_k (1 - p_k)$. For the favourite at $n = 250$ steps the mean is $200$, the SD is $\sqrt{250 \cdot 4 \cdot 0.9 \cdot 0.1} = \sqrt{90} \approx 9.5$. So horse $20$ is comfortably past $200$ by $n \approx 250$. For horse $19$ ($p = 0.88$) at the same $n$, mean position $= 250 \cdot 0.76 = 190$, SD $\approx \sqrt{250 \cdot 4 \cdot 0.88 \cdot 0.12} \approx 10.3$; horse $19$ still has a meaningful chance to be ahead.

A closed-form for each horse’s win probability would require the joint distribution of $20$ first-hitting times of a common boundary by asymmetric random walks, which has no clean expression. The accepted answer comes from Monte Carlo simulation; we encode the race directly and report empirical frequencies.

The computation

Encode the race: tick the clock, step every horse independently, and record the first to reach $200$. If two horses cross the line on the same tick, break the tie uniformly. Average over many races to get the win probabilities.

import random

P = [0.50 + 0.02*k for k in range(1, 21)]      # p_1..p_20

def race(rng):
    pos = [0] * 20
    while True:
        for i in range(20):
            pos[i] += 1 if rng.random() < P[i] else -1
        winners = [i for i in range(20) if pos[i] >= 200]
        if winners:
            return rng.choice(winners)

rng = random.Random(0)
TRIALS = 20_000
counts = [0] * 20
for _ in range(TRIALS):
    counts[race(rng)] += 1
for k, c in enumerate(counts):
    if c:
        print(f"horse {k+1:2d} (p={P[k]:.2f}): "
              f"wins {c}/{TRIALS} = {100*c/TRIALS:.2f}%")
# horse 15 (p=0.80): wins     2/20000 =  0.01%
# horse 16 (p=0.82): wins    19/20000 =  0.10%
# horse 17 (p=0.84): wins   152/20000 =  0.76%
# horse 18 (p=0.86): wins   948/20000 =  4.74%
# horse 19 (p=0.88): wins  4290/20000 = 21.45%
# horse 20 (p=0.90): wins 14589/20000 = 72.94%

A typical $20{,}000$-race run gives Horse $20$ around $70$–$74\%$, Horse $19$ around $20\%$, Horse $18$ around $5\%$, Horse $17$ around half a percent, and essentially nothing for any horse with index $\le 16$. (Horse $1$’s chance is roughly $10^{-32}$, far below sampling precision.)