combinatorial curiosities
Puzzles.
Counting problems that bite back.
24 live pieces
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? The exact probability approaches 1/e ≈ 36.8% as the number of items grows.
Ballot problem
A gets a votes, B gets b. P(A strictly ahead throughout) = (a−b)/(a+b). Proved by reflection.
Galton board
Balls through pegs. The binomial builds itself as a bell in real time.
100 prisoners and boxes
Follow permutation cycles and explain why coordinated success is not independent.
100 prisoners and hats
One parity bit makes every answer after the first certain.
Waiting for HH vs HT
Track overlapping pattern states and distinguish first waiting times from frequency.
Longest run of heads
In n coin flips, how long is the longest streak? The answer grows like log₂ n.
Broken stick
Break a stick twice at random. The pieces form a triangle exactly 1/4 of the time.
Balls in bins
Throw n balls into n bins. Max load grows like ln n / ln ln n.
Power of two choices
Pick two bins at random, take the lesser-loaded. Max load collapses to ln ln n.
Riffle shuffle
Measure how a random cut-and-interleave shuffle approaches uniform permutations.
Pólya's urn
Reinforcement changes future draws while the expected urn fraction stays fixed.
Ehrenfest urn
Moving one ball flips parity; allowing a hold changes convergence.
Sicherman dice
A non-standard pair of dice with the same sum distribution as 2d6.
Banach's matchbox
Count what remains when a pocket is first discovered empty.
Records in a permutation
Reveal record highs and derive their harmonic expected count.
Optimal house-selling
Compare each offer with the expected value of continuing.
Random walks in 1D, 2D, 3D
Compare finite return probabilities with recurrence in one and two dimensions and transience in three.
Kruskal count
Counting paths merge when they reach the same card; contact is not guaranteed.