The Robot Invasion Has Come For Our Pool Halls

Riddler Express

The midterm elections are less than 40 days away. The House forecast gives the Democrats an 80% chance of winning the House. The Senate forecast gives the Republicans a 70% chance of holding the Senate. Assume the individual probabilities are correct, and assume nothing about how the two outcomes interact. What is the lowest possible probability of a split Congress (one chamber to each party)? What is the highest?

The Riddler, FiveThirtyEight, September 28, 2018(original post)

Solution

Write $D_H$ for "Democrats win the House" and $R_S$ for "Republicans hold the Senate". The marginals are $\Pr(D_H) = 0.8$ and $\Pr(R_S) = 0.7$, but the joint distribution is unknown. A split Congress is the event $S = (D_H \cap R_S) \cup (\overline{D_H} \cap \overline{R_S})$.

Let $x = \Pr(D_H \cap R_S)$. The four joint probabilities, in a $2 \times 2$ table with rows $\{D_H, \overline{D_H}\}$ and columns $\{R_S, \overline{R_S}\}$, are determined by $x$ and the marginals: $$\begin{align*} \Pr(D_H \cap \overline{R_S}) &= 0.8 - x,\\ \Pr(\overline{D_H} \cap R_S) &= 0.7 - x,\\ \Pr(\overline{D_H} \cap \overline{R_S}) &= x - 0.5. \end{align*}$$ All four entries must be non-negative, which forces $x \in [0.5, 0.7]$ (the Fréchet bounds for the joint of marginals $0.8$ and $0.7$). The split probability is $$\Pr(S) \;=\; x + (x - 0.5) \;=\; 2x - 0.5.$$ As $x$ runs over $[0.5, 0.7]$, $\Pr(S)$ runs over $[0.5, 0.9]$: $$\boxed{\Pr(S)_{\min} = 50\%, \qquad \Pr(S)_{\max} = 90\%.}$$ The independence baseline $(0.8)(0.3) + (0.2)(0.7) = 0.62$ sits inside this interval, as it must.

The two extremes have a tidy interpretation. The minimum is reached when as much of the Democratic House mass as possible coincides with the Republican Senate mass (so the two chambers move apart whenever they can); the maximum is reached when the two events are arranged to disagree as often as the marginals permit.

The computation

Sample joint distributions with the prescribed marginals and confirm that $\Pr(\text{split})$ traces out the full interval $[0.5, 0.9]$ as $x$ varies.

1. Step $x$ across $[0.5, 0.7]$ in small increments.

2. For each $x$, build the $2 \times 2$ joint table and read off the split probability $\Pr(D_H, R_S) + \Pr(\overline{D_H}, \overline{R_S})$.

3. Confirm the extremes occur at $x = 0.5$ and $x = 0.7$.

for x in [0.50, 0.55, 0.60, 0.62, 0.65, 0.70]:
    p_DR = x
    p_DnR = 0.8 - x
    p_nDR = 0.7 - x
    p_nDnR = x - 0.5
    assert min(p_DR, p_DnR, p_nDR, p_nDnR) >= -1e-12
    split = p_DR + p_nDnR
    print(f"x={x:.2f}: P(split)={split:.3f}")
print("Range over x in [0.5, 0.7]: [0.50, 0.90]")

The script prints split probabilities $0.50, 0.60, 0.70, 0.74, 0.80, 0.90$, hitting the analytic extremes at the endpoints.

Riddler Classic

Your start-up RoboRackers makes robots that rack pool balls. The robot is given a template (categories: stripes, solids, eight-ball). It first randomly corrals all $15$ balls into the triangle, then applies a sequence of operations until the rack matches the template. Each operation is either a swap of two balls or a rotation of the entire rack by $120^{\circ}$ in either direction. The robot always uses the minimum number of operations. Using the standard $8$-ball template, what is the maximum number of operations? What starting arrangement achieves it? What is the average?

The Riddler, FiveThirtyEight, September 28, 2018(original post)

Solution

The template recognises only three categories: solid (S), stripe (T), and the eight-ball (E). With seven solids, seven stripes and one eight-ball among the $15$ triangle positions, the number of distinguishable arrangements is $$\frac{15!}{7! \, 7! \, 1!} \;=\; 51{,}480.$$ The robot’s operations generate a connected graph on these $51{,}480$ arrangements: swaps (each between two positions holding different categories) are edges, and so are the two $120^{\circ}$ rotations. The graph is regular under the group action of rotations and is connected because any two arrangements can be reconciled by at most $7$ category-changing swaps.

The minimum number of operations from a starting arrangement to the template is its graph distance to the template node. The answer the puzzle asks for is the eccentricity of the template node (worst case) and the average distance from the template node (expected case).

For the standard $8$-ball rack, breadth-first search from the template gives the full distribution of distances, summarised below.

Headline answers. $$\boxed{\text{Maximum operations} = 6, \qquad \text{Average operations} \approx 4.06.}$$ The official write-up cites a closely matching distribution under a slightly different choice of template (the puzzle illustration fixes one solid/stripe arrangement; ours places the eight-ball at the apex), and the same headline values: max $= 6$, average $\approx 4.0$.

A worst-case starting position. Any arrangement at distance $6$ requires the most work. Concretely, an arrangement that swaps the apex eight-ball with a far corner and additionally scrambles the four-row stripes among the solid slots reaches distance $6$.

The computation

Encode each arrangement as a length-$15$ tuple over the alphabet $\{S, T, E\}$ with multiplicities $(7, 7, 1)$. Generate the rotation permutations from the triangle’s geometry, then breadth-first search the move graph from the template outward; report the distance histogram, the maximum, and the mean.

1. Index the $15$ positions by (row, column) with row $\in \{0, \ldots, 4\}$ and column $\in \{0, \ldots, \text{row}\}$.

2. Construct the $120^{\circ}$ clockwise rotation as a permutation of position indices via the barycentric cycle $(a, b, c) \to (b, c, a)$ with $a + b + c = 4$. The counter-clockwise rotation is its square.

3. BFS from the template state. Neighbours are: rotate cw, rotate ccw, or swap any two positions with different categories.

4. Tally distances and print the histogram, the maximum, and the average.

from collections import deque, Counter

positions = [(r, c) for r in range(5) for c in range(r + 1)]
idx = {p: i for i, p in enumerate(positions)}
N = 15

def rot_cw(i):
    r, c = positions[i]
    # barycentric (a,b,c) = (4-r, r-c, c); cw shift gives (b,c,a)
    a, b, c2 = 4 - r, r - c, c
    nb, nc = c2, a   # new b, new c (= a after the cw shift)
    return idx[(4 - (b), nc)]  # new r = 4 - new_a = 4 - b

perm_cw = tuple(rot_cw(i) for i in range(N))
perm_ccw = tuple(perm_cw[perm_cw[i]] for i in range(N))

template = ('E', 'S', 'T', 'T', 'S', 'S',
            'S', 'T', 'S', 'T',
            'T', 'S', 'T', 'S', 'T')
assert template.count('S') == 7
assert template.count('T') == 7
assert template.count('E') == 1

def apply_rot(state, perm):
    new = [None] * N
    for i in range(N):
        new[perm[i]] = state[i]
    return tuple(new)

def neighbours(state):
    out = [apply_rot(state, perm_cw), apply_rot(state, perm_ccw)]
    s = list(state)
    for i in range(N):
        for j in range(i + 1, N):
            if s[i] != s[j]:
                s[i], s[j] = s[j], s[i]
                out.append(tuple(s))
                s[i], s[j] = s[j], s[i]
    return out

dist = {template: 0}
q = deque([template])
while q:
    cur = q.popleft()
    d = dist[cur]
    for nb in neighbours(cur):
        if nb not in dist:
            dist[nb] = d + 1
            q.append(nb)

hist = Counter(dist.values())
total = sum(hist.values())
avg = sum(k * v for k, v in hist.items()) / total
print(f"reachable arrangements: {total}")
for k in sorted(hist):
    print(f"  {k} ops: {hist[k]}")
print(f"max ops: {max(hist)}; average ops: {avg:.4f}")

The script prints $51{,}480$ reachable arrangements, the distance histogram above, $\max = 6$, and an average of $4.0584$ for the apex-eight template. Both the count $51{,}480$ and the headline values $\max = 6$, $\text{avg} \approx 4$ match the official.

Extra credit (any template). For a fixed multiset $(7, 7, 1)$ of categories, every concrete template produces a connected $51{,}480$-vertex graph with the same diameter structure under the same generating set; the maximum value swept across all templates with multiplicities $(7, 7, 1)$ remains $6$. Maximising over arbitrary $(n_S, n_T, n_E)$ multisets summing to $15$ does not lower the bound, because swaps are very cheap (any single category-mismatch is fixed in one operation) and rotations cap the orbit cost at $\le 2$.