vi. Classic Puzzles

Famous puzzles that keep showing up as contest problems or as the core of one. Each comes with its answer, the technique, and the general lesson.

Problems, not algorithms

These are questions whose answers happen to be famous — distinct from 🐬 Named Algorithms, which are methods. The full catalogue of named classic problems lives in 🐬 Classic Problems; every puzzle with an algorithmic core and its own dense note lives in 25. Puzzles.

Josephus problem

$n$ people in a circle; every $k$-th is eliminated. With 0-indexed survivor position $J$:

$J(1)=0,J(n)=(J(n-1)+k)\mathrm{mod}n.$

ll josephus(ll n, ll k) {                 // O(n)
    ll r = 0;
    for (ll i = 2; i <= n; i++) r = (r + k) % i;
    return r;
}
ll josephusFast(ll n, ll k) {             // O(k log n), for huge n and small k
    if (n == 1) return 0;
    if (k == 1) return n - 1;
    if (k > n) return (josephusFast(n - 1, k) + k) % n;
    ll c = n / k, r = josephusFast(n - c, k) - n % k;
    return r < 0 ? r + n : r + r / (k - 1);
}

• $k=2$: write $n$ in binary and rotate the leading 1 to the end, so the 1-indexed survivor is $2(n-2^{\lfloor {\log }_{2}n\rfloor })+1$ (proof below).
• Elimination order: keep the survivors in a Fenwick tree and find the $j$-th remaining by BIT descent, $O(n\log n)$; or use an order-statistics tree.
• Lesson: when a recurrence adds a constant modulo a growing bound, batch the steps that don’t wrap. josephusFast above is this batching: each “wrap” of the modulus roughly multiplies the working index by $\frac{k}{k-1}$, so only $O(k\log n)$ wraps occur before the index shrinks to 1.
• Named for Flavius Josephus, who (per his own account of the Jewish–Roman war) survived a forced lottery-style elimination among trapped companions by working out where the safe positions were.

Proof sketch: the $k=2$ closed form

Write $n=2^m+l$ with $0\le l<2^m$. One elimination pass removes every even 1-indexed position, leaving the $2^m+l-\lceil (2^m+l)/2\rceil$ survivors at odd positions $1,3,5,\dots$; relabelling them $1,2,3,\dots$ in order is itself a Josephus instance on the remaining count, except that when $n$ is odd the last elimination wraps around and removes position 1 too, shifting the relabelling by one. Unrolling this one bit at a time, starting from the leading bit of $n$, is exactly “rotate the leading 1 of $n$‘s binary representation to the end” — each remaining bit of $l$ determines one more step of the relabelling shift, giving survivor $2l+1$. The full inductive argument (and tested code) is in the dedicated Josephus note. $■$

Tower of Hanoi

$T(n)=2T(n-1)+1=2^n-1$ moves, and that’s optimal. Move $i$ (1-indexed) moves disk $\mathrm{ctz}(i)$ — exactly a Gray code: the bit that changes from $i$ to $i+1$ is $\mathrm{ctz}(i+1)$, and each disk’s position is one bit of it. Small disks cycle in a fixed direction (A$\to$C$\to$B for odd $n$). Reve’s puzzle with 4 pegs: the Frame-Stewart algorithm moves $k$ disks aside with 4 pegs, the rest with 3, minimising over $k$; it uses about $2^{\sqrt{2n}}$ moves. The state graph of $n$ disks is the Sierpinski graph (diameter $2^n-1$), and BFS on it handles any start and target configuration — the shortest path between two arbitrary configurations is computable in $O(n)$ by a greedy recursion, but is not always $2^n-1$; that is only the corner-to-corner distance. The ctz fact generalises: whenever a recursive process splits as $T(n)=2T(n-1)+O(1)$ and produces a sequence, that sequence usually has a description in terms of the binary expansion of the step index. Full derivation and tested code: Tower of Hanoi.

Water jugs

Capacities $a,b$; measure $c$. Possible iff $c\le \max (a,b)$ and $\gcd (a,b)\mid c$ (Bézout — the same fact that governs linear Diophantine equations and the Frobenius coin problem). Construct by repeatedly filling $a$ and pouring into $b$ (emptying $b$ when full), which walks through $a,2a,3a,\dots \mathrm{mod}b$. For the minimum number of operations, BFS over $(x,y)$ states, $O(ab)$. The famous Die Hard instance: $a=3,b=5,c=4$; since $\gcd (3,5)=1\mid 4$, it’s solvable.

Lesson: whenever a puzzle asks for the minimum number of operations, it is BFS on an implicit graph — the only real work is defining the state and the neighbour function:

Problem	State	Moves
water jugs	$(x,y)$ litres	fill, empty, pour
15-puzzle	board configuration	slide a tile
wolf, goat, cabbage	who is on which bank	cross with $\le 1$ item
missionaries and cannibals	counts on each bank	cross with 1-2 people
Rubik’s cube	cube state	face turn
word ladder	a word	change one letter
coin/token puzzles	positions	legal move
lock combinations	current code	rotate a dial

For very large state spaces, bidirectional BFS halves the exponent.

Variants: with 3+ jugs the gcd condition generalises to the gcd of all capacities; jugs with markings just add more moves, still BFS; minimising the water used (rather than the number of pours) is Dijkstra with pour amounts as edge weights; measuring $c$ in one specific jug restricts the goal test. Full derivation and tested code: Water Jug.

Wolf, goat, cabbage and missionaries

States are subsets on each bank plus the boat side (16 states for the 4-item version); BFS finds the 7-crossing solution and proves it optimal. Missionaries and cannibals (3+3, boat of 2, 32 states) needs 11 crossings; the 4-and-4 version with the same 2-person boat is unsolvable, which BFS discovers immediately and is tedious to argue by hand. Lesson: encode the state, encode the forbidden states, BFS.

When the state space is too large for plain BFS: a hash set or bitset of visited states scales to $\sim 10^7$; bidirectional BFS to $\sim 10^{14}$; beyond that, A*/IDA* with a good heuristic, or pattern databases. If the state has symmetries (interchangeable items, reflections), canonicalising each state before hashing can shrink the search by a large constant factor. Tested code: Wolf, Goat, Cabbage.

Bridge and torch

$n$ people, a torch, at most two on the bridge. Sort times ascending. While more than 3 remain, move the two slowest using the cheaper of

• the fastest escorts each: $2t_0+t_{n-1}+t_{n-2}$;
• the two fastest ferry: $t_0+2t_1+t_{n-1}$.

Finish with 3 people ($t_0+t_1+t_2$), 2 ($t_1$) or 1 ($t_0$). For $\{1,2,5,10\}$ the answer is 17 (the naive “fastest shuttles everyone” gives 19). Proof by exchange: the two slowest should cross together, and only the two fastest ever return. A bitmask DP over (who crossed, torch side) checks the greedy on small inputs.

Variants: a boat holding $k>2$ keeps the greedy shape but makes it harder to prove (DP is safer); different return costs, or some people unable to cross together, both need the full DP; minimising the number of crossings instead of total time is $2n-3$ for $n\ge 2$; multiple torches changes the structure entirely; a torch with a limited lifetime adds a feasibility check. This belongs to the same family as wolf/goat/cabbage, missionaries and cannibals, “jealous husbands” (a pairing constraint), and river crossing with a raft of capacity $k$ — all state-space searches, with bridge-and-torch unusual in also having a clean greedy. Whenever an obvious greedy feels forced, ask whether pairing the two worst items beats handling them separately — the same idea appears in Huffman coding. Full derivation and tested code: Bridge and Torch.

100 prisoners

Each of 100 prisoners may open 50 of 100 boxes. Strategy: start at your own number’s box and follow the permutation’s cycle. Everyone succeeds iff no cycle is longer than 50:

$P=1-{\sum }_{k=51}^{100}\frac{1}{k}\approx 0.3118,{\lim }_{n\to \infty }=1-\ln 2.$

Lesson: correlating failures beats independent strategies, and the cycle structure of a random permutation is very predictable. A random permutation has $H_n$ cycles on average, and a given element lies in a cycle of length $\ell$ with probability exactly $1/n$ for every $\ell$. Curtin and Warshauer (2006) proved cycle-following is not merely clever but provably optimal — no strategy does better.

The transferable idea is correlating failures: independent strategies multiply probabilities ($\prod p_i$, decaying exponentially), while cycle-following makes every prisoner’s fate depend on the same event, collapsing the product to one probability. The same trick recurs elsewhere:

Setting	Correlation trick
hat-guessing puzzles	agree on a parity convention ($n-1$ of $n$ always correct, vs. $n/2$ expected independently)
distributed consensus	shared randomness
derandomisation	replace independent bits with pairwise-independent ones
coupon collector variants	coordinate the sampling

Further permutation-cycle facts worth knowing on their own: expected number of fixed points is $1$; $\mathrm{Pr}[\text{longest cycle}>n/2]=\ln 2$; the expected length of the longest cycle is $\approx 0.6243n$ (the Golomb–Dickman constant); the expected length of the cycle containing a fixed element is $(n+1)/2$; and the number of permutations with exactly $k$ cycles is counted by the (unsigned) Stirling numbers of the first kind. The same “follow the permutation” idea is also a real algorithmic technique: in-place permutation application (apply $\sigma$ with $O(1)$ extra space by walking cycles), cycle sort (minimum swaps to sort $=n-$number of cycles), permutation parity ($(-1{)}^{n-c}$), and computing ${\sigma }^k$ per cycle by rotation — see also cycle detection in functional graphs.

Proof: $\mathrm{Pr}[\text{a uniform random permutation of }n\text{ elements has a cycle of length exactly }\ell ]=1/\ell$

Count permutations containing a cycle of length exactly $\ell$: choose which $\ell$ elements form it ($\left(\genfrac{}{}{0ex}{}{n}{\ell }\right)$ ways), arrange them into a single cycle ($(\ell -1)!$ distinct cyclic orders), and permute the remaining $n-\ell$ elements arbitrarily ($(n-\ell )!$ ways). That’s $\left(\genfrac{}{}{0ex}{}{n}{\ell }\right)(\ell -1)!(n-\ell )!$ permutations, out of $n!$ total:
$\mathrm{Pr}=\frac{\left(\genfrac{}{}{0ex}{}{n}{\ell }\right)(\ell -1)!(n-\ell )!}{n!}=\frac{n!}{\ell !(n-\ell )!}\cdot \frac{(\ell -1)!(n-\ell )!}{n!}=\frac{(\ell -1)!}{\ell !}=\frac{1}{\ell }.$
For $\ell >n/2$, two disjoint cycles of length $\ell$ would need $>n$ elements, so at most one such cycle can exist — meaning “has a cycle of length $\ell$” and “has exactly one cycle of length $\ell$” coincide, and these events for different $\ell >n/2$ are mutually exclusive (a permutation has at most one cycle longer than $n/2$). So $\mathrm{Pr}[\text{failure}]=\mathrm{Pr}[\text{some cycle has length}>n/2]={\sum }_{\ell =n/2+1}^n\mathrm{Pr}[\text{a cycle of length }\ell \text{ exists}]={\sum }_{\ell =n/2+1}^n\frac{1}{\ell }=H_n-H_{n/2}$, matching the formula above. $■$

Tested: the closed-form failure probability $H_n-H_{n/2}$ checked against a direct Monte Carlo simulation (generate random permutations, run the cycle-following strategy, measure the empirical failure rate) converging to the predicted $\approx 0.3118$ for $n=100$.

A random permutation also has $H_n\approx \ln n$ cycles on average, and $\mathrm{Pr}[\text{no fixed point}]\to 1/e$ as $n\to \infty$ (see derangements). Full derivation, optimality proof and tested code: 100 Prisoners.

Monty Hall

Switching wins with probability $2/3$. The host’s knowledge is what matters: he always opens a goat door, so he gives no information about your door. Solve any variant with Bayes or by enumerating the joint distribution.

Host behaviour	$\mathrm{Pr}[\text{win by switching}]$
always opens a goat door (standard)	$2/3$
opens a random door; it happened to be a goat	$1/2$
offers a switch only when you picked the car	$0$
offers a switch only when you picked a goat	$1$
opens a goat but prefers the lower-numbered door when free	$1/2$ or $1$, depending on which he opened

The puzzle is famous less for the $2/3$ answer than for how much it depends on this unstated host protocol — conditional probability depends on the process that generated the information, not just on the information itself. Related puzzles with the same lesson, each with its own dedicated note where one exists: the boy-or-girl paradox (“at least one boy” gives $1/3$; “the older is a boy” gives $1/2$ — identical stated fact, different conditioning), Bertrand’s box (three boxes of coins, answer $2/3$ not $1/2$), Sleeping Beauty (the reference class is genuinely ambiguous), the two envelopes problem (the naive switching argument is flawed), the base-rate fallacy (a rare disease with an accurate test still yields mostly false positives), and the prosecutor’s fallacy ($\mathrm{Pr}[E\mid I]\ne \mathrm{Pr}[I\mid E]$). Full derivation and tested code: Monty Hall.

Secretary problem

$n$ candidates come in random order and you must accept or reject each on the spot. Reject the first $r\approx n/e$, then take the first candidate better than all seen. That succeeds with probability $\to 1/e$. Variants: maximising the expected rank needs a threshold rule that changes with time (expected rank $\to 3.87$); with $k$ choices allowed use multiple thresholds. These are the classic examples of online algorithms and optimal stopping, solved by backward DP over “candidates remaining”. The constant $1/e$ recurs throughout online decision-making (online bipartite matching, submodular-maximisation greedy, balls-into-bins), and the related prophet inequality (values drawn from known distributions) gives a $1/2$-competitive threshold rule. Full derivation, the full variants table and the online-algorithms/competitive-ratio connection: Secretary Problem.

Poisoned wine and group testing

One of $n$ bottles is poisoned and tasters die after a fixed delay. With one round, $\lceil {\log }_{2}n\rceil$ tasters suffice: taster $j$ drinks the bottles with bit $j$ set, and the dead tasters spell the bottle’s index. With $t$ rounds a taster’s outcome is “dies in round $\mathrm{1..}t$ or survives”, so $\lceil {\log }_{t+1}n\rceil$ tasters suffice (2 rounds and 3 tasters handle 27 bottles instead of 8). Lesson: the information-theoretic bound ${\log }_{(\text{outcomes})}(\text{possibilities})$, and binary encoding as a construction. With $d$ poisoned bottles, $\left(\genfrac{}{}{0ex}{}{n}{d}\right)$ outcomes must be distinguished and non-adaptive group-testing designs need $O(d^2\log n)$ tasters; if waiting between rounds is free, plain binary search solves $d=1$ with one taster and $\lceil {\log }_{2}n\rceil$ days. Full derivation and tested code: Poisoned Wine.

Counterfeit coin with a balance

Each weighing has 3 outcomes. With the heavier/lighter direction unknown, $k$ weighings handle $(3^k-3)/2$ coins (12 coins in 3 weighings); if a known-genuine reference coin is available, $(3^k-1)/2$. With a known-heavier fake, $3^k$ coins. Lesson: ternary search and information bounds. Full derivation and tested code: Counterfeit Coin.

Celebrity problem

Find the person everyone knows who knows no one, using knows(a, b) queries. Keep a candidate $c$. For each $i$, if knows(c, i) then $c$ isn’t the celebrity, so set $c=i$. Then verify $c$ with $2(n-1)$ queries. At most $3(n-1)$ queries in total, $O(n)$ — and this is close to optimal, since $3n-\Theta (\log n)$ queries are provably necessary in the worst case. Lesson: one comparison eliminates one candidate; with $n^2$ possible relationships, the answer is pinned down by examining only $O(n)$ of them. Modelling “knows” as a directed graph, a celebrity is exactly a vertex with in-degree $n-1$ and out-degree $0$: reading the full adjacency matrix finds it in $O(n^2)$ by summing rows and columns, but the $O(n)$ elimination algorithm never reads most of the matrix. At most one celebrity can exist (two would each have to know the other, contradicting “knows no one”). The same pattern finds a sink in a tournament.

Egg dropping, stairs, coins

These are the canonical DPs; see Classic DP. Egg dropping inverts nicely: $f(t,k)$ = the most floors decidable with $t$ throws and $k$ eggs satisfies $f(t,k)=f(t-1,k-1)+f(t-1,k)+1={\sum }_{i=1}^k\left(\genfrac{}{}{0ex}{}{t}{i}\right)$.

Grid and board puzzles

Puzzle	Technique
8/15-puzzle	solvability by permutation parity + blank row; IDA* with Manhattan + linear conflict (Informed Search)
Lights Out	linear system over ${\mathbb{F}}_2$; or fix the first row ($2^m$ choices) and chase the rest, $O(2^{m}nm)$ or $O((nm{)}^3/64)$
N-queens	bitmask backtracking; constructions exist for every $n\ne 2,3$
Knight’s tour	Warnsdorff’s rule; closed tours exist on $m\times n$ boards unless $m,n$ both odd, or $m\in \{1,2,4\}$, or $m=3$ with $n\in \{4,6,8\}$
Sudoku	exact cover with dancing links, or bitmask backtracking choosing the most constrained cell
Peg solitaire / Conway’s soldiers	colouring and weight invariants
Pancake sorting	at most $2n-3$ flips with the obvious greedy; the optimum is NP-hard
Domino and tromino tilings	colouring for impossibility; broken-profile DP to count; Kasteleyn’s formula for domino tilings of planar grids
Königsberg bridges	Euler path iff 0 or 2 odd vertices

Number puzzles

Puzzle	Answer
trailing zeros of $n!$ in base 10	${\sum }_i\lfloor n/5^i\rfloor$; in base $b=\prod q^e$, ${\min }_q\lfloor v_q(n!)/e\rfloor$ (Legendre)
Chicken McNugget (coprime $a,b$)	largest non-representable $ab-a-b$; exactly $(a-1)(b-1)/2$ non-representable values
last non-zero digit of $n!$	recurse on $n/5$ with a period-10 table, or compute $n!/10^z\mathrm{mod}10$ by splitting into factors of 2 and 5
number of digits of $n!$	$\lfloor \sum {\log }_{10}i\rfloor +1$, or Kamenetsky’s formula via Stirling
first $k$ digits of $a^b$	$10^{\{b{\log }_{10}a\}}$
derangements ($n$ items, none in its own place)	$D_n=n!{\sum }_{k=0}^n(-1{)}^k/k!$, see inclusion–exclusion
staircase / ways to climb $n$ steps taking 1 or 2 at a time	Fibonacci
counting brackets, triangulations, BSTs, mountain ranges	all Catalan numbers $C_n$, see Catalan
digit sums, repunits, palindromic numbers in a range	digit DP, see Digit DP

Cross-reference: puzzle name $\to$ technique

Puzzles that are really just a named instance of a technique covered in full elsewhere.

Puzzle	Technique
Maximum subarray	Kadane, Classic Array Problems
Trapping rain water	two pointers or monotonic stack, Monotonic Stack
Largest rectangle in a histogram	monotonic stack
Majority element	Boyer–Moore voting
Dutch national flag	three-way partition
Gas station / circular tour	greedy with a running deficit
Stock buy and sell	greedy, or DP by transaction count
Next greater element	monotonic stack
Knapsack, coin change, rod cutting	DP, see Knapsack (coin change: greedy fails in general; rod cutting is unbounded knapsack)
Assignment problem	Hungarian algorithm, $O(n^3)$, see Assignment Problem
Stable marriage	Gale–Shapley, $O(n^2)$, see Stable Matching
Travelling salesman	NP-hard; Held–Karp for $n\le 20$, see Hamiltonian Paths and TSP
Subset sum / partition	NP-hard in general; pseudo-polynomial DP when values are small