The Perfect Doodle Puzzle To Keep You Busy During Boring Meetings

Riddler Express

A centrifuge needs to be perfectly balanced along every axis before being run; otherwise, the torque will damage the internal rotor. If a centrifuge has $N$ equally spaced buckets, some of which you fill with $K$ samples of equal weight, for what values of $K$ can all the samples be spun safely? Hint: you can run seven samples in a $12$-bucket centrifuge, but you cannot run ten in a $21$-bucket centrifuge.

The Riddler, FiveThirtyEight, July 27, 2018(original post)

Solution

Place the buckets at the $N$-th roots of unity in the complex plane: position $k$ is the point $\zeta^{k}$ where $\zeta = e^{2 \pi i / N}$, for $k = 0, 1, \ldots, N-1$. The centrifuge is balanced exactly when the centre of mass of the filled buckets sits at the origin, that is, when the chosen subset $S \subseteq \{0, 1, \ldots, N-1\}$ satisfies $$\sum_{k \in S} \zeta^{k} \;=\; 0.$$ So the question is purely combinatorial: which subset sizes $K = |S|$ are realisable as a zero-sum multiset of $N$-th roots of unity?

Two building blocks work straight away. First, if $p$ is a prime divisor of $N$, the $p$ evenly spaced positions $0,\, N/p,\, 2N/p, \ldots, (p-1)N/p$ form a regular $p$-gon centred at the origin, so $p$ samples balance. Second, if one subset of size $a$ balances and a disjoint subset of size $b$ balances, their union balances too, contributing $a + b$ samples. By picking different regular $p$-gons (rotating them to avoid overlap, which is always possible when there is room) we can realise any sum of prime divisors of $N$.

The converse is the heart of the matter and is a classical result on vanishing sums of roots of unity, due to Rédei and Lam-Leung: a multiset of $N$-th roots of unity sums to zero if and only if it decomposes into regular $p$-gons for primes $p \mid N$. Counting samples, this is the same as saying $K$ is expressible as a non-negative integer combination of the prime divisors of $N$. Apply the same criterion to the unfilled buckets to get the symmetric requirement on $N - K$.

The two hint cases drop out: for $N = 12$, the prime divisors are $\{2, 3\}$, and $K = 7 = 2+2+3$ with $N-K = 5 = 2+3$, so seven samples work. For $N = 21$, the prime divisors are $\{3, 7\}$, and although $K = 10 = 3+7$, the complement $N-K = 11$ is not a non-negative combination of $3$ and $7$, so ten samples cannot balance. Two edge cases also follow: $K = 1$ and $K = N-1$ never balance (a single sample is off-centre by itself, and so is a single hole), and a prime $N$ admits no balanced load other than the trivial $K = 0$ and $K = N$.

The computation

Verify the criterion exhaustively against the geometric definition for all $(N, K)$ with $N \le 12$: for each $K$-subset of the $N$ roots of unity, check whether its centroid is at the origin, and compare with the prime-decomposition criterion.

import itertools
from cmath import exp, pi

def primes(n):
    ps, m, d = set(), n, 2
    while d * d <= m:
        while m % d == 0:
            ps.add(d); m //= d
        d += 1
    if m > 1: ps.add(m)
    return sorted(ps)

def reachable(target, ps):
    R = [False] * (target + 1); R[0] = True
    for p in ps:
        for v in range(p, target + 1):
            if R[v - p]: R[v] = True
    return R[target]

def by_criterion(N, K):
    ps = primes(N)
    return reachable(K, ps) and reachable(N - K, ps)

def by_brute(N, K):
    if K in (0, N): return True
    roots = [exp(2j * pi * k / N) for k in range(N)]
    for S in itertools.combinations(range(N), K):
        if abs(sum(roots[k] for k in S)) < 1e-9:
            return True
    return False

bad = 0
for N in range(2, 13):
    for K in range(0, N + 1):
        if by_criterion(N, K) != by_brute(N, K):
            bad += 1
print(f"mismatches for N=2..12: {bad}")
print(f"(N=12, K=7)  -> {by_criterion(12, 7)}")
print(f"(N=21, K=10) -> {by_criterion(21, 10)}")

The script prints $0$ mismatches, confirms the $12,7$ case as balanceable, and confirms the $21,10$ case as not.

Riddler Classic

Start with an empty $5 \times 5$ grid of squares. Choose any square as your starting square. From any square you may move exactly three cells horizontally or vertically, or exactly two cells diagonally; you may not visit any cell twice; you may not step off the grid. You win if you visit all $25$ cells. Is it possible to win? If so, how many winning tours are there? And what is the shortest dead-end you can be forced into?

The Riddler, FiveThirtyEight, July 27, 2018(original post)

Solution

The legal moves from a square at $(r, c)$ are the eight offsets $(\pm 3, 0)$, $(0, \pm 3)$, $(\pm 2, \pm 2)$. A Hamiltonian path is a sequence of distinct squares connected by these moves that visits all $25$ cells. The state space is small enough to enumerate by depth-first search with backtracking. There are at most $25$ choices for the starting square and at most $8$ moves at each step, so the worst-case tree has size bounded above by $25 \cdot 8^{24}$, but most branches die quickly because of the no-revisit rule and the boundary.

A backtracking search returns $$\boxed{12{,}400 \text{ winning tours, so a Hamiltonian path exists.}}$$ The starting square matters: there are $552$ winning tours from each corner, $548$ from each edge midpoint not adjacent to a corner, $552$ or $548$ from the other boundary squares, $412$ from the second-ring corners, $400$ from the second-ring edge midpoints, and only $352$ from the centre. The centre is the worst start, with $200$ fewer tours than a corner.

Two structural features make the centre weak. First, both diagonal moves from the centre land on second-ring corners, which is where the moves concentrate, so the centre’s neighbourhood is small (six legal moves). Second, the move graph has a parity: colour the squares with $(r + c) \bmod 2$, and the orthogonal move keeps the colour while the diagonal move flips it. A tour of all $25$ squares hits $13$ of one colour and $12$ of the other, and the parity sequence imposed by the move sequence has to match; starts in the centre give fewer parity-respecting completions.

A second backtracking pass tracks the shortest dead-end length, where a dead-end is a partial tour with no legal next move. The shortest dead-end has length $\boxed{8}$, reached by $32$ distinct partial tours.

The computation

Two depth-first searches, one for the tour count and one for the shortest dead-end length.

1. For every starting square $(r, c)$, depth-first-search all Hamiltonian paths, incrementing a global counter on each success.

2. Track, across all runs, the shortest partial tour length at which no legal next move exists.

N = 5
MOVES = [(3, 0), (-3, 0), (0, 3), (0, -3),
         (2, 2), (2, -2), (-2, 2), (-2, -2)]

total = 0
per_start = {}
shortest_stuck = 25

def dfs(r, c, visited):
    global total, shortest_stuck
    if len(visited) == 25:
        total += 1; return
    moved = False
    for dr, dc in MOVES:
        nr, nc = r + dr, c + dc
        if 0 <= nr < N and 0 <= nc < N and (nr, nc) not in visited:
            moved = True
            visited.add((nr, nc))
            dfs(nr, nc, visited)
            visited.remove((nr, nc))
    if not moved and len(visited) < shortest_stuck:
        shortest_stuck = len(visited)

for sr in range(N):
    for sc in range(N):
        before = total
        dfs(sr, sc, {(sr, sc)})
        per_start[(sr, sc)] = total - before

print(f"total Hamiltonian tours: {total}")
print(f"shortest dead-end length: {shortest_stuck}")
print("tours per start square (rows top->bottom):")
for sr in range(N):
    print([per_start[(sr, sc)] for sc in range(N)])

The script prints $12{,}400$ tours total, shortest dead-end length $8$, and the per-start table given above with $552$ at corners and $352$ in the centre.