Can You Break A Very Expensive Centrifuge?

The Riddler for September 18, 2020. The Express balances seven tubes around a twelve-slot centrifuge, and the Classic finds the expected number of guesses in an optimal binary search through a dictionary.

Riddler Express

A microcentrifuge has $12$ slots evenly spaced around a circle. For it to stay balanced, the centre of mass of the loaded tubes (all equal mass) must sit at the exact centre. You need to spin exactly seven tubes. In which of the slots ($1$ through $12$) can you place them so the centrifuge is balanced?

The Riddler, FiveThirtyEight, September 18, 2020(original post)

Solution

Put the slots at the twelfth roots of unity. The tubes balance exactly when the sum of their slot vectors is zero. A vanishing sum of twelfth roots decomposes into rotated regular polygons whose vertex counts are the prime divisors of $12$: diametrically opposite pairs (two vectors $180^\circ$ apart) and equilateral triangles (three vectors $120^\circ$ apart). So a balanced set of size $7$ must be a disjoint union with $2a + 3b = 7$. Since $7$ is odd, $b$ is odd; $b = 1$ forces $a = 2$. Every balanced seven-tube layout is therefore one equilateral triangle plus two diametric pairs, for example slots $$\boxed{\{1, 2, 5, 6, 8, 9, 12\}}$$ (the triangle $\{1, 5, 9\}$ together with the pairs $\{2, 8\}$ and $\{6, 12\}$). Counting them: there are $4$ rotations of the triangle, and removing one triangle leaves exactly $3$ intact diametric pairs from which to choose $2$, so $4 \times \binom{3}{2} = 12$ balanced arrangements in all (all rotations of one another). Equivalently, placing seven tubes is the same as choosing the five empty slots, the balanced-five problem.

The computation

Encode the balance condition directly: a subset is balanced when its slot vectors (twelfth roots of unity) sum to zero. Enumerate all seven-slot subsets and count.

import itertools, cmath
roots = [cmath.exp(2j * cmath.pi * k / 12) for k in range(12)]
balanced = [c for c in itertools.combinations(range(12), 7)
            if abs(sum(roots[k] for k in c)) < 1e-9]
print(len(balanced))                                 # 12
ex = balanced[0]
print(tuple(k + 1 for k in ex))                      # a 1-indexed layout

Exactly $12$ seven-tube layouts balance, each a triangle plus two diametric pairs.

Riddler Classic

In the game Guess My Word, a secret word is drawn uniformly from a dictionary of exactly $267{,}751$ entries. After each guess you learn whether the secret word is alphabetically before or after it. Playing as efficiently as possible, how many guesses should you expect to need?

The Riddler, FiveThirtyEight, September 18, 2020(original post)

Solution

The optimal strategy is binary search: guess the middle word, and recurse into whichever half the answer lies in. This builds a binary tree in which one word is found on guess $1$, two words on guess $2$, four on guess $3$, and in general $2^{d-1}$ words on guess $d$, as long as that many words remain. The full levels run from $d = 1$ to $d = 18$, covering $1 + 2 + \cdots + 2^{17} = 2^{18} - 1 = 262{,}143$ words; the remaining $267{,}751 - 262{,}143 = 5{,}608$ words sit on guess $19$. Averaging over the uniformly random secret word, $$\begin{aligned} E &= \frac{1}{267{,}751}\left(\sum_{d=1}^{18} d\,2^{d-1} + 19 \cdot 5{,}608\right)\\ &= \frac{4{,}563{,}001}{267{,}751} \approx \boxed{17.042 \text{ guesses}}. \end{aligned}$$ This sits just above $\log_2(267{,}751) \approx 18.03 - 1$: binary search on $N$ items averages a hair under $\log_2 N$ guesses because some words are found early.

The computation

Encode the tree level by level: $2^{d-1}$ words are resolved on guess $d$ until the dictionary is exhausted, then take the weighted mean.

from fractions import Fraction
N = 267_751
depth, remaining, total = 1, N, 0
while remaining > 0:
    count = min(2**(depth - 1), remaining)   # words found on guess `depth`
    total += depth * count
    remaining -= count
    depth += 1
E = Fraction(total, N)
print(E, float(E))                           # 4563001/267751  17.0419...

The expected number of guesses is $4{,}563{,}001/267{,}751 \approx 17.042$.