Classic brainteasers

Quant probability has a canon of brainteasers that has been stable for decades: the coupon collector, the hundred prisoners, the drunk passenger, the broken stick. The canon endures because each problem isolates a single powerful technique — linearity over stages, cycle structure, symmetry, an invariant, a geometric picture. This chapter solves the canon twice over: the thirty-second answer that nails the number, and the rigorous argument that survives “prove it.”

✦Intuition — classify before you compute

Almost every classic yields to one of five moves. (1) Linearity + indicators or stages: decompose the quantity into pieces whose expectations are easy (random variables & moments). (2) Symmetry: find an exchangeable structure that makes outcomes equally likely. (3) Recursion / first-step analysis: condition on the first move (Markov chains). (4) Invariant: find something the randomness cannot change. (5) Geometry: map uniform randomness to area or volume. Say which move you are making out loud — the classification is worth as much as the arithmetic.

The coupon collector#

Problem. Each trial produces one of $n$ equally likely coupon types, independently. How many trials $T$ until you have collected all $n$ types?

Fast answer. Break the collection into stages. While you hold $i - 1$ distinct types, each trial is “new” with probability $p_{i} = (n - i + 1) / n$ , so the stage length is geometric with mean $1/ p_{i}$ . Linearity of expectation sums the stages — no independence between stages needed:

E [T] = i = 1 \sum n \frac{n}{n - i + 1} = n (1 + \frac{1}{2} + \dots + \frac{1}{n}) = n H_{n} \approx n ln n + 0.577 n .

Worked number: for a die, $E [T] = 6 (1 + \frac{1}{2} + \dots + \frac{1}{6}) = 14.7$ rolls to see every face.

✦Rigorous — variance and concentration

The stage lengths $T_{i}$ are independent (each stage restarts the Bernoulli structure), so variances add. A geometric with success probability $p$ has variance $(1 - p) / p^{2}$ , hence

Var (T) = i = 1 \sum n \frac{1 - p _{i}}{p _{i}^{2}} < n^{2} k = 1 \sum n \frac{1}{k ^{2}} n \to \infty \frac{π ^{2}}{6} n^{2},

so the standard deviation is of order $n$ — much smaller than the mean $n ln n$ , which is why the collection time concentrates. For the tail, a union bound over coupons gives $P (T > n ln n + c n) \leq n (1 - 1/ n)^{n l n n + c n} \leq e^{- c}$ — the classic $n ln n + c n$ threshold. Compare the tail-bound machinery in inequalities & tail bounds.

Histogram of simulated coupon-collector completion times for n = 50 with the mean n H_n marked, showing right skew and concentration around n log n — Simulated coupon-collector times. The distribution sits near n ln n with standard deviation of order n — the mean n H_n (line) is a reliable summary, but the right tail is real: the last few coupons dominate the wait.

The 100 prisoners and the boxes#

Problem.100 prisoners’ names are placed in 100 boxes, one per box, uniformly at random. Each prisoner may open 50 boxes, looking for their own name; no communication after the search starts. All must succeed or all die. Random guessing gives success probability $(1/2)^{100} \approx 8 \times 1 0^{- 31}$ . Find a strategy with success probability over 30%.

Fast answer. The boxes define a permutation $π$ (box $i$ contains name $π (i)$ ). Strategy: follow the cycle — prisoner $i$ opens box $i$ , then the box labelled by the name found, and so on. Prisoner $i$ is walking the cycle of $π$ containing $i$ and finds their name in exactly (cycle length) steps. Everyone succeeds iff the longest cycle has length $\leq 50$ . The failure probability is the chance of a cycle longer than 50, and cycles longer than $n /2$ are unique, so their probabilities add.

✦Rigorous — the probability a cycle of length k exists

Count permutations of $n$ elements containing a cycle of length $k > n /2$ : choose the cycle’s elements $(k n)$ ways, arrange them in a cycle $(k - 1)!$ ways, permute the rest $(n - k)!$ ways:

P (a k -cycle exists) = \frac{( k n ) ( k - 1 )! ( n - k )!}{n !} = \frac{1}{k}, k > \frac{n}{2} .

These events are disjoint (two cycles longer than $n /2$ cannot coexist), so with $n = 100$ :

P (fail) = k = 51 \sum 100 \frac{1}{k} = H_{100} - H_{50} \approx 0.6882, P (success) \approx 0.3118.

As $n \to \infty$ the failure probability tends to $ln 2 \approx 0.693$ , so the success probability tends to $1 - ln 2 \approx 0.307$ — it does not decay with $n$ . The strategy works by correlatingthe prisoners’ fates: they fail together or succeed together, converting a product of small probabilities into a single event about cycle structure.

Diagram of a permutation decomposed into cycles, with the follow-the-cycle strategy path highlighted and the success probability versus longest cycle length — The permutation's cycle decomposition decides everyone's fate at once. Following the cycle starting at your own box always finds your name in exactly cycle-length steps — so success is the single event {longest cycle <= 50}, which has probability about 31%.

prisoners_sim.py

import numpy as np

rng = np.random.default_rng(11)

def longest_cycle(perm):
    seen = np.zeros(perm.size, dtype=bool)
    best = 0
    for i in range(perm.size):
        length, j = 0, i
        while not seen[j]:
            seen[j] = True
            j = perm[j]
            length += 1
        best = max(best, length)
    return best

trials = 20_000
wins = sum(longest_cycle(rng.permutation(100)) <= 50 for _ in range(trials))
print(f"follow-the-cycle success: {wins / trials:.4f}")            # ~0.312
print(f"theory 1 - (H_100 - H_50): {1 - np.sum(1 / np.arange(51, 101)):.4f}")
print(f"random guessing:          {0.5 ** 100:.1e}")               # 7.9e-31

The drunk passenger (airplane seat)#

Problem. 100 passengers board a full plane in order. Passenger 1 has lost their boarding pass and sits in a uniformly random seat. Every later passenger takes their own seat if free, otherwise a uniformly random free seat. What is the probability passenger 100 gets their own seat?

Answer: $1/2$ — and it earns three proofs, in ascending rigor.

Symmetry. Every person who chooses randomly is choosing uniformly among free seats, and seats 1 and 100 are both free until one of them is taken (taking seat 1 ends all displacement; taking seat 100 dooms the last passenger). Each random chooser treats the two symmetrically, so seat 1 is taken before seat 100 with probability $1/2$ — and passenger 100 gets their seat exactly when seat 1 goes first.
Recursion. Let $p_{n}$ be the answer for $n$ passengers. Passenger 1 picks seat 1 (probability $1/ n$ , success certain), seat $n$ (probability $1/ n$ , failure certain), or seat $k$ with $2 \leq k \leq n - 1$ — in which case passengers 2 through $k - 1$ sit normally and passenger $k$ becomes a new drunk passenger in a plane of $n - k + 1$ seats. So $p_{n} = \frac{1}{n} + \frac{1}{n} \sum_{k = 2}^{n - 1} p_{n - k + 1}$ ; with $p_{2} = 1/2$ , induction gives $p_{n} = 1/2$ for all $n \geq 2$ .
Invariant. At every moment before the last boarding, at most one passenger is displaced, and the process ends the first time a random chooser picks seat 1 or seat 100. Whatever the history, the next random pick is uniform over a free set containing both terminal seats — so the stopped state is a fair coin no matter the path. This is a baby optional-stopping argument: the conditional probability of ending at “seat 1 first” is a martingale pinned at $1/2$ .

✦Rigorous — the variant: which passengers get displaced?

For passenger $k \geq 2$ of $n$ , the relay of random choices made before $k$ boards ends the first time a chooser picks a seat in $A = {1} \cup {k, k + 1, \dots, n}$ : seat 1 stops all displacement, seat $k$ displaces passenger $k$ , and any seat $j > k$ pauses the relay until after $k$ has boarded safely. Each random choice is uniform over free seats, so by symmetry every element of $A$ is equally likely to be hit first:

P (passenger k displaced) = \frac{1}{∣ A ∣} = \frac{1}{n - k + 2} .

Sanity checks: $k = 2$ gives $1/ n$ (only if passenger 1 sat there directly), $k = n$ gives $1/2$ — the original answer falls out as a special case.

The broken stick#

Problem. Break a unit stick at two points chosen independently and uniformly. What is the probability the three pieces form a triangle?

Fast answer. A triangle forms iff no piece exceeds $1/2$ (triangle inequality). The three events “piece $i$ exceeds $1/2$ ” are disjoint and each has probability $1/4$ : the left piece is long iff both cuts land in the right half ( $\frac{1}{2} \cdot \frac{1}{2}$ ), the right piece symmetrically, and the middle piece is long iff the cuts are more than $1/2$ apart — the two corner triangles of the unit square, total area $1/4$ . So $P (triangle) = 1 - 3 \cdot \frac{1}{4} = \frac{1}{4}$ .

✦Rigorous — the geometric region

Let the cuts be $(U, V)$ , uniform on the unit square. Condition on $U < V$ (probability $1/2$ , symmetric case identical). The pieces are $U, V - U, 1 - V$ , and all three are below $1/2$ iff

U < \frac{1}{2}, V > \frac{1}{2}, V - U < \frac{1}{2},

a triangle of area $1/8$ inside the half-square of area $1/2$ . Doubling over the two orderings gives total probability $2 \cdot \frac{1}{8} = \frac{1}{4}$ . Beware the classic bait-and-switch variant: break the stick, then break the longer piece — the sampling scheme changes and the answer becomes $2 ln 2 - 1 \approx 0.386$ . Always ask how the randomness is generated.

The two envelopes#

Problem. Two envelopes hold $m$ and $2 m$ . You pick one, see amount $X$ , and reason: “the other holds $2 X$ or $X /2$ with probability $1/2$ each, so its expected value is $\frac{1}{2} (2 X) + \frac{1}{2} (X /2) = 1.25 X$ — I should always swap.” And having swapped, the same logic says swap back. Where is the error?

Fast answer. Work in terms of the pair, not the observed amount: the two envelopes contain $m$ and $2 m$ , you hold each with probability $1/2$ , so both “keep” and “swap” have expected value $\frac{3}{2} m$ . Swapping gains exactly zero by symmetry.

✦Rigorous — the conditioning error

The fallacy is the step $P (smaller ∣ X = x) = \frac{1}{2} for every x$ . That conditional probability depends on the prior over $m$ : by Bayes, it equals $π (x) / (π (x) + π (x /2))$ where $π$ is the density of the smaller amount. For it to be $1/2$ at every $x$ you would need $π (x) = π (x /2)$ for all $x$ — a “uniform on all scales” prior, which integrates to infinity and is not a probability distribution. Under any proper prior, seeing $X = x$ carries information: large $x$ makes “you hold the bigger one” more likely, and the conditional expected gain from swapping integrates to exactly zero. The paradox is a disguised lesson in conditioning: expectations computed against an improper implicit prior are not expectations.

How many uniforms to exceed 1?#

Problem. Draw $U_{1}, U_{2}, \dots$ iid uniform on $[0, 1]$ and let $N = min {n : U_{1} + \dots + U_{n} > 1}$ . Find $E [N]$ .

Fast answer. Use the tail-sum formula (proved in random variables & moments) plus the simplex volume $P (U_{1} + \dots + U_{n} \leq 1) = 1/ n!$ :

E [N] = n = 0 \sum \infty P (N > n) = n = 0 \sum \infty \frac{1}{n !} = e \approx 2.718.

✦Rigorous — the simplex volume by induction

Claim: $F_{n} (t) := P (U_{1} + \dots + U_{n} \leq t) = t^{n} / n!$ for $t \in [0, 1]$ . Base case $F_{1} (t) = t$ . Inductive step, conditioning on the last draw:

F_{n} (t) = \int_{0}^{t} F_{n - 1} (t - u) d u = \int_{0}^{t} \frac{( t - u ) ^{n - 1}}{( n - 1 )!} d u = \frac{t ^{n}}{n !} .

Geometrically this is the volume of the corner simplex ${u_{i} \geq 0, \sum u_{i} \leq t}$ . Then $P (N > n) = F_{n} (1) = 1/ n!$ and the tail sum telescopes into the series for $e$ . Bonus fact for the follow-up: the expected overshoot and the full distribution $P (N = n) = \frac{n - 1}{n !}$ follow from differencing the tails.

Buffon’s needle#

Problem. Drop a needle of length $L$ on a floor ruled with parallel lines a distance $d \geq L$ apart. What is the probability the needle crosses a line?

Fast answer. Quote and verify the answer $2 L / (π d)$ : for $L = d$ it is $2/ π \approx 0.637$ , and it scales linearly in $L$ — as it must, since for a short needle the expected number of crossings is additive over segments (linearity again: bend the needle into any shape of total length $L$ and the expected crossing count is unchanged — “Buffon’s noodle”).

✦Rigorous — integrate over position and angle

Let $x \sim U [0, d /2]$ be the distance from the needle’s centre to the nearest line and $θ \sim U [0, π /2]$ its acute angle to the lines, independent. The needle crosses iff $x \leq \frac{L}{2} sin θ$ . Since $L \leq d$ ,

P (cross) = E [\frac{( L /2 ) sin θ}{d /2}] = \frac{L}{d} \cdot \frac{2}{π} \int_{0}^{π /2} sin θ d θ = \frac{2 L}{π d} .

Dropping needles and counting crossings therefore estimates $π$ — the original Monte-Carlo method, two centuries early. The modern toolkit for such estimators (standard errors, variance reduction) is in simulation & Monte Carlo.

Three quick classics#

Three ants on a triangle. Each ant sits on a vertex and walks along a randomly chosen adjacent edge. Fast: no collision iff all three walk clockwise or all counterclockwise — $2/ 2^{3} = 1/4$ . Rigorous: the 8 direction-choices are equally likely; any mixed choice puts two ants on one edge head-on or into the same vertex — enumerate to confirm exactly 2 of 8 outcomes are collision-free. On an $n$ -gon the same argument gives $2/ 2^{n} = 2^{1 - n}$ .

Tigers and sheep. 100 perfectly rational tigers and one sheep. A tiger that eats the sheep becomes a sheep itself (and can then be eaten); every tiger prefers eating to not eating, but survival above all. Does the sheep get eaten? Fast: parity. Rigorous: induct on the number of tigers $T$ . $T = 1$ : the tiger eats — no threat remains. $T = 2$ : eating would leave the eater as a sheep facing one tiger, who (by the base case) eats — so neither moves; the sheep is safe. In general the sheep is eaten iff $T$ is odd, since eating hands the next mover the $T - 1$ position. With $T = 100$ (even) the sheep survives. The technique — backward induction over a shrinking game — is the same first-step analysis you use for hitting-time problems.

Birthday collisions. With $n$ people and $M = 365$ days, fast: pairs collide, and there are $(2 n)$ pairs each colliding with probability $1/ M$ , so $P (collision) \approx 1 - e^{- n (n - 1) /2 M}$ — about $1/2$ at $n = 23$ . Rigorous: the exact probability is $1 - \prod_{k = 0}^{n - 1} (1 - k / M)$ ; taking logs and using $ln (1 - x) \approx - x$ recovers the exponential form with error $O (n^{3} / M^{2})$ . The full derivation is in counting & combinatorics; what matters here is the square-root law: collisions appear once $n \approx 1.2 M$ .

→Quant lens — birthday collisions are why strategy zoos overfit

Replace people with strategy variants and days with effectively-independent ways a backtest can look good. Test $N$ variants and you are running $(2 N) \approx N^{2} /2$ implicit pairwise comparisons — coincidences (two variants sharing the same lucky trades, a variant matching the benchmark’s best year) arrive on the $M$ scale, quadratically faster than intuition expects. Meanwhile the best-looking of $N$ zero-edge strategies shows a Sharpe growing like $2 ln N$ (derived in multiple testing & paradoxes). A grid search over 100 parameter settings is not 100 chances to find an edge — it is 4,950 chances to find a coincidence. This is the probabilistic core of why backtests lie and of overfitting detection.

The canon at a glance#

Problem	Answer	Key move
Coupon collector (n types)	n H_n ≈ n ln n + 0.577n	Geometric stages + linearity
100 prisoners, 50 boxes	≈ 31.2% (→ 1 − ln 2)	Cycle structure; disjoint long-cycle events
Drunk passenger, last seat	1/2	Symmetry of seats 1 and n / invariant
Broken stick triangle	1/4	Geometry in the unit square
Uniforms to exceed 1	e	Tail-sum + simplex volume 1/n!
Buffon's needle (L = d)	2/π ≈ 0.637	Integrate over position and angle
Three ants, no collision	1/4 (n-gon: 2^{1−n})	Enumerate; only unanimous directions work
Tigers and sheep (T = 100)	Sheep survives (even T)	Parity + backward induction

Speed round#

→Problem 1 — Same semicircle

Three points are chosen uniformly at random on a circle. What is the probability all three lie in some semicircle?

Solution. For each point $i$ , let $A_{i}$ be the event that the semicircle starting at point $i$ and running clockwise contains the other two points. The $A_{i}$ are disjoint (only the clockwise-first point of a containing semicircle can start it), and each has probability $(1/2)^{2} = 1/4$ . So the answer is $3 \cdot 1/4 = 3/4$ . For $n$ points the same disjoint-union argument gives $n / 2^{n - 1}$ . The slick move — turning “some semicircle” into a disjoint union indexed by which point leads — is the insight worth articulating.

→Problem 2 — First six wins

You and an opponent alternate rolling a fair die; you roll first. The first player to roll a 6 wins. What is your probability of winning?

Solution. Let $p$ be your winning probability. You win now with probability $1/6$ ; otherwise (probability $5/6$ ) your opponent becomes the first mover, winning with probability $p$ , so you win with $1 - p$ : $p = \frac{1}{6} + \frac{5}{6} (1 - p) \Rightarrow p = \frac{6}{11}$ . Slicker: your winning rolls are attempts $1, 3, 5, \dots$ , giving the geometric series $\frac{1}{6} \sum_{k} (\frac{25}{36})^{k}$ — but the fastest framing is that consecutive attempts’ win odds decay by a factor $5/6$ , so the odds are $6 : 5$ in your favour.

→Problem 3 — Cards until the first ace

Cards are dealt one at a time from a well-shuffled 52-card deck. What is the expected number of cards dealt up to and including the first ace?

Solution. Symmetry: the 4 aces split the other 48 cards into 5 exchangeable gaps, so each gap has expected size $48/5$ . The first ace arrives after the first gap: $E = \frac{48}{5} + 1 = 10.6$ . Rigorous version: each non-ace card precedes all four aces with probability $1/5$ (uniform relative order of 5 cards), so by indicators the expected number of non-aces before the first ace is $48 \cdot \frac{1}{5}$ — the same exchangeability argument that powers order statistics.

→Problem 4 — Drunk passenger, passenger 60

In the 100-passenger drunk-passenger setup, what is the probability that passenger 60 gets their own seat?

Solution. By the relay argument above, passenger $k$ is displaced with probability $1/ (n - k + 2)$ : the relay of random choices ends at the first pick from the $n - k + 2$ symmetric seats ${1, k, k + 1, \dots, n}$ , and only seat $k$ hurts them. With $n = 100, k = 60$ : $P (own seat) = 1 - \frac{1}{42} = \frac{41}{42} \approx 0.976$ . Early passengers are nearly safe; the danger concentrates on the last few seats.

Next: from puzzles to inference — what it means to estimate a quantity from data, and how to judge one estimator against another. Estimators & sampling theory.