Chapter 206

The Riddler Just Had To Go And Reinvent Beer Pong

Riddler Express

Two grandmasters play a World Chess Championship match. The better player wins each game with probability $0.20$ , loses with probability $0.15$ , and draws with probability $0.65$ . Wins count $1$ point, draws $0.5$ each, losses $0$ . The match is $N$ games; the first to $N/2 + 0.5$ points wins the match outright (ties don’t decide the title here). What are the chances the better player wins a $12$ -game match? How many games does the match need to give the better player a $75\%$ , $90\%$ , or $99\%$ chance of winning outright?

The Riddler, FiveThirtyEight, November 16, 2018(original post)

Solution

A game contributes $+1$ , $0$ , or $-1$ to the margin (better player’s score minus opponent’s, in units of half points doubled). The better player wins the match outright when the margin after $N$ games is strictly positive. The match outcome is the sign of $\sum_{i=1}^{N} g_{i}$ with $g_{i} \in \{+1, 0, -1\}$ and probabilities $\begin{aligned} \Pr(g = +1) &\,=\, 0.20, \\ \Pr(g = \phantom{+}0) &\,=\, 0.65, \\ \Pr(g = -1) &\,=\, 0.15. \end{aligned}$

Generating function. Encode each game by the Laurent polynomial $f(x) = 0.20 \, x + 0.65 + 0.15 \, x^{-1}$ . The match polynomial is $f(x)^{N}$ ; the coefficient of $x^{r}$ is the probability the margin equals $r$ . The match-win probability is the sum of coefficients on the positive powers of $x$ : $\Pr(\text{better player wins } N\text{-game match}) \;=\; \sum_{r \ge 1} [x^{r}] \, f(x)^{N}.$ This is a clean polynomial computation: expand $f(x)^{N}$ and sum the positive-exponent coefficients.

$N = 12$ . Direct expansion gives $\Pr(\text{12-game win}) \;\approx\; \mathbf{52.0\%}.$ For the thresholds, scan $N$ upwards and stop at the first $N$ exceeding each target: $N = \mathbf{82} \text{ for } 75\%, \quad N = \mathbf{248} \text{ for } 90\%, \quad N = \mathbf{773} \text{ for } 99\%.$

Sanity check. The expected margin per game is $0.20 - 0.15 = 0.05$ , and the variance is $0.20 + 0.15 - 0.05^{2} = 0.3475$ . By the central limit theorem, the margin after $N$ games is approximately Gaussian with mean $0.05 \, N$ and standard deviation $\sqrt{0.3475 \, N}$ , and the match-win probability is $\Phi \!\left( \frac{0.05 \, N}{\sqrt{0.3475 \, N}} \right) \;=\; \Phi \!\left( 0.0848 \sqrt{N} \right).$ For $N = 12$ this is $\Phi(0.294) \approx 0.616$ (overshoots a little, as the Gaussian approximation does for a discrete margin near zero). For $\Phi^{-1}(0.75) = 0.674$ , solving $0.0848 \sqrt{N} = 0.674$ gives $N \approx 63$ ; the true value $82$ exceeds it by about $30\%$ , since for moderate $N$ the discreteness of the margin (mass at $0$ , then jumps by $1$ ) and the long tail of draws sit far enough from the asymptotic Gaussian shape that the threshold integer is meaningfully larger.

The computation

Build $f(x)^{N}$ by iterated polynomial multiplication and sum the coefficients on the positive exponents. Use Python integers and rationals to avoid floating-point drift over large $N$ .

Represent the running polynomial as a dictionary $\{r: \Pr(\text{margin} = r)\}$ .
Multiply by $f$ each game: shift mass by $+1$ with weight $0.20$ , leave with $0.65$ , shift by $-1$ with $0.15$ .
Sum positive-exponent mass for the answer.

from collections import defaultdict

def p_win(N):
    coef = {0: 1.0}
    for _ in range(N):
        nxt = defaultdict(float)
        for r, c in coef.items():
            nxt[r + 1] += 0.20 * c
            nxt[r]     += 0.65 * c
            nxt[r - 1] += 0.15 * c
        coef = nxt
    return sum(c for r, c in coef.items() if r > 0)

print(f"N = 12: P(win) = {p_win(12):.4f}")
for target in (0.75, 0.90, 0.99):
    N = 1
    while p_win(N) < target:
        N += 1
    print(f"target {target:.2f}: smallest N = {N}")

The script prints $0.5198$ for $N = 12$ and the thresholds $82$ , $248$ , $773$ , matching the boxed answer.

Riddler Classic

The game has $N$ cups labelled $1$ through $N$ and an infinite supply of balls each labelled $1$ through $N$ (uniformly random per ball). Each round has two phases. In the throwing phase the player takes balls one at a time from the supply and throws them; each throw lands in a uniformly random cup; the phase ends when every cup contains at least one ball. In the pruning phase the player goes through each cup and removes every ball whose number does not match the cup’s label. The game ends after a round in which no cup is empty after the pruning. How many rounds is the game expected to take? How many throws?

The Riddler, FiveThirtyEight, November 16, 2018(original post)

Solution

After each round, every cup ends either locked (holding at least one ball whose label matches the cup, kept by pruning forever) or open (empty after pruning). Locked cups remain locked since their kept balls satisfy the no-empty-cup termination criterion for free in subsequent rounds. Let $K_{t}$ be the number of locked cups at the end of round $t$ . The game ends at the first $t$ with $K_{t} = N$ .

Throws per round. Suppose round $t + 1$ starts with $K_{t} = k$ locked cups. Locked cups already have a matching ball, so the throwing phase already has them in the "non-empty" state. The phase continues until each of the remaining $N - k$ open cups receives at least one ball. Each throw goes uniformly to one of $N$ cups, so the round’s throw count $T$ is the cover time for the $N - k$ open cups: $\mathbb{E}[T \mid k] \;=\; \sum_{j=1}^{N - k} \frac{N}{j}.$ The largest term, when only one open cup remains, contributes $N$ throws by itself. The sum grows like $N \ln(N - k)$ for $k \ll N$ .

Locking new cups. Each open cup that receives at least one ball this round has independent probability $1/N$ that the ball matches the cup label, and the cup might receive several balls (each independently matching with probability $1/N$ ). Let $M_{i}$ be the number of balls received by open cup $i$ in this round; the cup locks iff at least one of those $M_{i}$ balls matches, with probability $1 - (1 - 1/N)^{M_{i}}$ given $M_{i}$ .

The exact joint distribution of $(M_{1}, \ldots, M_{N - k})$ given $T$ throws is the multinomial restricted to all positive counts. A clean closed form is not at hand, but the round dynamics are easy to simulate, and the asymptotic structure is clear:

The number of rounds grows roughly linearly with $N$ : each round locks an expected $\Theta(1)$ new cups on average among the open ones, since open cup $i$ receives $\Theta(\ln N)$ balls in a typical round when many cups are still open, each matching independently with probability $1/N$ , so the match probability per round is $\Theta((\ln N)/N)$ . Multiplied by $N - k$ open cups, the expected new locks per round is $\Theta(\ln N)$ , and $\sum_{k} 1 / \Theta(\ln N) \sim N$ rounds.
The number of throws grows roughly quadratically with $N$ : each round costs $\Theta(N \ln N)$ throws (cover time on the open cups), and there are $\Theta(N)$ rounds, for $\Theta(N^{2} \ln N)$ total.

For concrete numbers, a simulation gives $\mathbb{E}[\text{rounds}] \approx 8.3$ and $\mathbb{E}[\text{throws}] \approx 58.8$ at $N = 5$ ; $\approx 19.0$ rounds and $\approx 292.8$ throws at $N = 10$ . The ratio $\text{throws} / N^{2}$ is roughly $2.3$ at $N = 5$ and $2.9$ at $N = 10$ , consistent with the $\Theta(N^{2} \ln N)$ scaling.

The computation

Encode the round dynamics exactly and run $10^{4}$ trials per $N$ . Confirm rounds scale roughly linearly and throws roughly quadratically.

Maintain a Boolean vector locked[1..N].
Per round: draw labelled balls into uniform cups until every cup has at least one ball (locked or new).
For each new ball in cup $c$ , if its label equals $c$ set locked[c] to true.
Stop at the first round where all entries are locked.

import random
from statistics import mean

def play(N, rng):
    locked = [False] * N
    rounds = 0
    throws = 0
    while not all(locked):
        rounds += 1
        touched = list(locked)                       # locked cups count as non-empty
        new_balls = {i: [] for i in range(N) if not locked[i]}
        while not all(touched):
            label = rng.randrange(N)
            cup = rng.randrange(N)
            throws += 1
            touched[cup] = True
            if not locked[cup]:
                new_balls[cup].append(label)
        for cup, balls in new_balls.items():
            if any(b == cup for b in balls):
                locked[cup] = True
    return rounds, throws

rng = random.Random(0)
for N in (3, 5, 7, 10):
    samples = [play(N, rng) for _ in range(10_000)]
    er = mean(r for r, _ in samples)
    et = mean(t for _, t in samples)
    print(f"N={N}: E[rounds]~{er:.2f}, E[throws]~{et:.2f}, "
          f"throws/N^2~{et / N**2:.2f}")

The script confirms that the rounds count grows linearly and the throws count grows quadratically, with the constants slowly creeping up due to the $\ln N$ factor in the cover-time term.

Extra Credit

It’s been a while: time for a Coolest Riddler Extension Award. What if the game weren’t so simple? What if you could aim? What if you could miss? The most interesting twist on this game earns a shiny emoji trophy.

Solution

This is a participatory contest call (Coolest Riddler Extension), not a derivable mathematical question. Like the other community-submission Extras (the trap-effectiveness Express in chapter $204$ being the closest example), it is deferred.