combinatorial curiosities
Puzzles.
Counting problems that bite back.
7 live pieces
· 17
more on the way
Birthday problem
How many people before a shared birthday is more likely than not?
Coupon collector's problem
How many boxes to complete the set? E[T] = n·Hₙ — surprisingly large.
Buffon's needle
Drop needles on lined paper to estimate π. Watch the estimate converge.
Gambler's ruin
Two players bet until one goes bankrupt. Starting stake and bias determine the odds.
Secretary problem
Reject the first 37%, hire the next best. Optimal stopping at 1/e ≈ 37%.
Derangements
How likely that no hat returns to its owner? Approaches 1/e ≈ 36.8% for any n ≥ 6.
Ballot problem
A gets a votes, B gets b. P(A strictly ahead throughout) = (a−b)/(a+b). Proved by reflection.
Galton board
soon Balls through pegs. The binomial builds itself as a bell in real time.
100 prisoners and boxes
soon Each prisoner opens 50 of 100 boxes. A cycle strategy wins ~31% of the time.
100 prisoners and hats
soon Red or blue? Parity-based guessing saves 99 of the 100.
Waiting for HH vs HT
soon Both patterns have probability 1/4 — but one waits 6 flips and the other 4. Why?
Longest run of heads
soon In n coin flips, how long is the longest streak? The answer grows like log₂ n.
Broken stick
soon Break a stick twice at random. The pieces form a triangle exactly 1/4 of the time.
Balls in bins
soon Throw n balls into n bins. Max load grows like ln n / ln ln n.
Power of two choices
soon Pick two bins at random, take the lesser-loaded. Max load collapses to ln ln n.
Riffle shuffle
soon Seven shuffles to randomize a deck. Total variation distance plunges at step seven.
Pólya's urn
soon Draw a ball, add one of the same color. The long-run fraction is Beta-distributed.
Ehrenfest urn
soon Molecules swap between chambers. Reversible, recurrent, surprisingly slow to mix.
Sicherman dice
soon A non-standard pair of dice with the same sum distribution as 2d6.
Banach's matchbox
soon Two pockets, one empty. What is the distribution of what’s left in the other?
Records in a permutation
soon How many record highs in n random draws? Expected value is exactly Hₙ.
Optimal house-selling
soon Offers arrive one at a time from a known distribution. The threshold rule that maximizes.
Random walks in 1D, 2D, 3D
soon Pólya: recurrent in 1D and 2D, transient in 3D. Some drunks never find home.
Kruskal count
soon A card-path trick that almost always ends on the same card. Coupling in action.