The Builder's Tools

The kill shots end problems with one observation. These five tools do the opposite work: they construct — an answer, a tiling, a schedule, a strategy — piece by piece, with a proof riding along. Same format: definition, signal, worked pair, machines.

Induction, and the Art of Asking for More

The tool. Prove the base case; prove that each case forces the next. The non-obvious craft sits one level up: sometimes a statement P is unprovable by induction while a stronger statement sails through — because the inductive step gets to assume the hypothesis, and a stronger claim is also a stronger tool. Pólya named the effect the inventor's paradox: proving more can be easier. It is the single most counterintuitive lever in the beginner-to-olympian transition.

The smell. Any claim parameterized by n; recursive or self-similar structures — trees, tilings of 2ⁿ boards, nested expressions. The strengthening trigger is specific and worth memorizing: your inductive step almost works, but the hypothesis is too weak to push it through — it needs a fact the plain statement does not carry. The response is not to abandon induction. It is to load the statement with the missing cargo — a sharper bound, a more general configuration — and re-run.

★★ · The Sum of Odd Numbers

Prove that 1 + 3 + 5 + ⋯ + (2n − 1) = n².

Pause. Draw it before you prove it.

Solution. Base, n = 1: 1 = 1². Step: assume the sum to (2n − 1) is n²; add the next odd number: n² + (2n + 1) = (n + 1)². ∎ The picture is better than the algebra: an n × n square grows into an (n + 1) × (n + 1) square by wrapping an L-shaped shell of exactly 2n + 1 cells around two sides. Induction as the geometry of accretion.

The Move — Climb from n to n + 1. The plainest tool in the book — and the chassis every refinement below bolts onto.

★★★ · The Broken Board

Prove that every 2ⁿ × 2ⁿ board with any one cell missing can be tiled by L-trominoes (three cells in an L).

Pause here. Chapter 9 proved boards impossible; now build one.

Solution. The strengthening is already in the statement — and that is the lesson. The "natural" question (a corner missing) is harder to induct on: the quartered board hands you sub-boards with no missing corners, and the hypothesis has no grip. Prove the stronger "any cell" version instead. Base, n = 1: a 2 × 2 board minus any cell is an L-tromino. Step: split the 2ⁿ⁺¹ board into four 2ⁿ quadrants; the missing cell lies in one of them. Place a single tromino at the center, covering the corner cell of each of the other three quadrants. Now every quadrant is a 2ⁿ × 2ⁿ board missing exactly one cell — apply the stronger hypothesis four times. ∎ (Count check: (4ⁿ⁺¹ − 1)/3 = 4·(4ⁿ − 1)/3 + 1 — three quadrant-deficiencies manufactured, one tromino spent. ✓)

This is the constructive twin of Chapter 9's colorings: pigment proves impossibility, induction manufactures possibility.

The Move — Generalize until the step has a grip. A more general claim hands the inductive step more to hold onto. If quartering the problem produces sub-problems your hypothesis cannot touch, widen the hypothesis until it can.

★★★★ · A Cushion Made of Nothing

Prove that 1/1² + 1/2² + ⋯ + 1/n² < 2 for every n.

Pause. Try the obvious induction and watch it die.

Solution. The obvious induction: assume Sₙ < 2; then Sₙ₊₁ = Sₙ + 1/(n + 1)² < 2 + something. No room. The statement is true but inductively sterile — the hypothesis leaves nothing to absorb the new term.

Strengthen it: prove Sₙ ≤ 2 − 1/n. Base, n = 1: S₁ = 1 = 2 − 1. Step: given Sₙ ≤ 2 − 1/n, it suffices that 1/(n + 1)² ≤ 1/n − 1/(n + 1) = 1/(n(n + 1)), i.e. that n(n + 1) ≤ (n + 1)², i.e. that n ≤ n + 1. True. So Sₙ₊₁ ≤ 2 − 1/(n + 1), and in particular Sₙ < 2 for all n. ∎

The stronger claim carries its own fuel: the −1/n term is exactly the absorbing cushion the step needed. (Euler later showed the true limit is π²/6 ≈ 1.645 — our cushion is nowhere near tight, and that is fine. A strengthening need only be inductively closed, not sharp.)

The Move — Strengthen the hypothesis. An induction hypothesis is not what you must prove; it is what you get to use. When the step leaks, ask Pólya's inverted question: what stronger statement would make this step trivial?

Machines and this move. Hypothesis strengthening is lemma invention — the classic bottleneck of automated theorem proving, with heuristics but no reliable method — and models mimic famous strengthenings well while rarely originating the right generalization fresh; humans feel where the step leaks and patch the statement.

Recursion → Dynamic Programming

The tool. Express the answer to a problem in terms of answers to smaller instances; when subproblems repeat, cache them (memoization) or fill them bottom-up (dynamic programming). Textbooks sell DP as a technique. Competitors know it as a representation question: choose what a "state" is — the minimal summary of the past that the future needs — and the recurrence usually writes itself. The classical ladder climbs one dimension at a time: Fibonacci (one dimension — the ways to tile a 1 × n strip with 1s and 2s), grid paths (two), knapsack (a resource), bitmask DP (a set), digit and tree DP (structured prefixes).

The smell. "Count the ways…", "minimum cost to…", "longest … over sequences, grids, trees." The problem decomposes by "what was the last choice?" Brute force is exponential, but the relevant past is small. The professional's checklist, in order: What are the decisions? After a prefix of decisions, what does the future actually need to know? — that is the state. Transitions are one decision; the cost is #states × transition cost; and if that is too big, the state is carrying junk — compress it.

★★ · Twenty Paths

How many monotone paths — steps right and down only — run from the top-left to the bottom-right corner of a 4 × 4 lattice of nodes, from (0,0) to (3,3)?

Pause. Solve the top-left corner of the question first.

Solution. State: f(i, j) = the number of monotone paths reaching node (i, j). You arrived from above or from the left, so f(i, j) = f(i−1, j) + f(i, j−1), with the edges all 1. Fill the table:

Answer: 20. And look at the table — it is Pascal's triangle, tilted: f(i, j) = C(i+j, i), here C(6,3) = 20. ✓ ∎

The Move — Name the state, fill the table. The recursion ("the last step came from left or above") is trivial; the payoff is a closed form materializing out of a table. Dynamic programming as experimental mathematics.

★★★★ · The Knapsack, End to End

Capacity W = 8. Items: A (weight 2, value 3), B (3, 4), C (4, 5), D (5, 8). Maximize total value within the capacity — and know why the greedy fails.

Pause here. Try greed first, deliberately.

Solution. Greedy by value density: D = 1.6, A = 1.5, B ≈ 1.33, C = 1.25. Greed takes D (weight 5), then A (weight 2) — value 11, weight 7, nothing else fits. 11 is not optimal.

Now the DP. State: dp[c] = the best value achievable within capacity c, over the items processed so far; process items one by one, scanning c downward so each item is used at most once. Start all-zero.

• after A: dp = [0, 0, 3, 3, 3, 3, 3, 3, 3]
• after B: dp = [0, 0, 3, 4, 4, 7, 7, 7, 7] (e.g. dp[5] = max(3, dp[2] + 4) = 7)
• after C: dp = [0, 0, 3, 4, 5, 7, 8, 9, 9] (dp[6] = max(7, dp[2] + 5) = 8; dp[7] = max(7, dp[3] + 5) = 9)
• after D: dp = [0, 0, 3, 4, 5, 8, 8, 11, 12] (dp[7] = max(9, dp[2] + 8) = 11; dp[8] = max(9, dp[3] + 8) = 12)

Optimum 12 = B + D: weights 3 + 5 = 8, values 4 + 8 — the greedy's 11 loses to 12. (Verified against full enumeration of all 2⁴ subsets: the feasible bests are A+D = 11, B+D = 12, B+C = 9, A+C = 8.) Cost: 4 items × 9 capacities ≈ 36 cell-updates replace 16 subset checks — and at n = 100, W = 100,000, the same table replaces 2¹⁰⁰ subsets. One honest caveat: O(nW) is pseudo-polynomial — W is exponential in its own digit count — so knapsack remains NP-hard. ∎

The Move — Compress history into a sufficient statistic. The state is not "which items were taken" (2ⁿ states) but "how much capacity is spent" — because value is all the future needs and capacity is all the future is constrained by. Every hard DP is hard exactly here: longest-increasing-subsequence compresses "the whole prefix" to "smallest tail per length"; traveling-salesman DP compresses "the route so far" to "(visited set, current city)"; digit DP compresses "the number built" to "(position, still tight?, property so far)." The same move, up the ladder.

Machines and this move. The most machine-friendly tool in the arsenal — once states are defined, filling tables is what computers are, and the ladder saturates their training data; the residual human edge is state invention — spotting that an exotic history collapses to a small sufficient statistic.

Greedy, with the Exchange Argument

The tool. A greedy algorithm makes the locally best choice and never revisits it. Greed is usually wrong; when it is right, the standard proof is the exchange argument: take any optimal solution OPT, show you can swap one of its choices for the greedy's choice without making it worse, and induct — so the greedy's output matches OPT. (The deep-structure version says greedy is exactly optimal on matroids; competitors mostly wield the exchange lemma directly.)

The smell. Scheduling, selecting, merging, ordering — anywhere a sort by the right key feels plausible, and the future depends on the past only through a running total or frontier. The disciplined reflex is double-sided: hunt for the exchange and hunt for a counterexample with equal energy — small n, adversarial weights. If neither wins in ten minutes, suspect DP instead. And carry the warning shot every competitor eats early: coins {1, 3, 4}, amount 6. Greedy: 4 + 1 + 1, three coins. Optimal: 3 + 3, two. Greedy-with-proof or bust.

★★ · Picking Meetings

From the intervals [0,2), [1,3), [2,4), [3,5), [4,6), choose the maximum number that pairwise do not overlap.

Pause. Which key would you sort by?

Solution. The greedy rule: repeatedly take the interval with the earliest finish among those compatible with what you have. Trace: take [0,2); skip [1,3); take [2,4); skip [3,5); take [4,6) — 3 meetings, and 3 is the maximum (four pairwise-disjoint intervals of length 2 would need total length 8 in a span of 6).

The exchange proof of the rule: let g₁ be the earliest-finishing interval overall and o₁ the earliest element of any optimal set OPT. Then finish(g₁) ≤ finish(o₁), so OPT − {o₁} + {g₁} is still pairwise-disjoint — g₁ ends no later than o₁, so it cannot collide with the rest of OPT — and has the same size. Some optimum therefore starts with the greedy's choice; recurse on the remaining span. ∎

The Move — Morph the optimum into the greedy. The proof never says greedy beats OPT. It says OPT can be reshaped into the greedy, one lossless swap at a time — a template reusable across half of algorithmics.

★★★★ · The Largest Number

Given positive integers — say {9, 5, 34, 3, 30} — arrange them in a row so that the concatenation of their decimal digits is the largest possible number.

Pause here. The obvious sort is wrong; find the right comparator.

Solution. Sort by the comparator: x before y when the concatenation xy exceeds yx (compared as numbers). Trace: 9 vs 5 → "95" > "59"; 34 vs 3 → "343" > "334", so 34 precedes 3; 3 vs 30 → "330" > "303", so 3 precedes 30. Order: 9, 5, 34, 3, 30 — answer 9534330 (beating, for instance, 9, 5, 3, 34, 30 → 9533430).

Why this is legitimate — two obligations most solvers skip:

1. The comparator is a genuine total order. Writing X for x's value and ℓₓ for its digit-length: xy > yx ⟺ X·10^ℓʸ + Y > Y·10^ℓˣ + X ⟺ X(10^ℓʸ − 1) > Y(10^ℓˣ − 1) ⟺ X/(10^ℓˣ − 1) > Y/(10^ℓʸ − 1). The funny pairwise rule is secretly a sort by the single real key κ(x) = X/(10^ℓˣ − 1) — hence transitive, hence a valid sort. And κ has a lovely reading: κ(34) = 34/99 = 0.343434…, κ(3) = 3/9 = 0.333… — each number's digits repeated forever. The arrangement sorts by what you would become if you repeated without end.
2. Exchange for optimality. In any arrangement, if some adjacent pair sits against the comparator (…yx… where xy > yx), swapping them changes only that junction — every other digit keeps its position — and strictly increases the whole number. Any non-sorted arrangement contains such an adjacent inversion, so it is not optimal; the sorted arrangement is the maximum, with κ-ties interchangeable. ∎

The Move — Prove both duties. A greedy rule owes two debts: coherence (the comparator must be transitive — and a programming language will happily "sort" with a non-transitive one into nonsense) and exchange-stability. Pay both or don't submit.

Machines and this move. Language models propose greedy rules fluently and hallucinate their correctness; the {1, 3, 4} reflex — attacking your own rule before trusting it — is a trained adversarial habit, not a default.

Binary Search on the Answer

The tool. To optimize a quantity that is hard to compute directly, flip the question: is there a solution with value at least x? If feasibility is monotone in x — feasible at x implies feasible at everything on one side — then the optimum is a threshold, and binary search finds it with O(log range) calls to a decision procedure. You have traded "optimize" for "decide," and deciding is almost always easier: a greedy or a graph check.

The smell. The magic words: minimize the maximum, maximize the minimum — "largest minimum distance," "smallest time by which all jobs finish." Also: the answer is a single number in a bounded range, and checking a candidate is easy even though producing the best one is not. The reflex: ask "if an oracle whispered the answer x, could I verify a solution at level x cheaply?" If yes, and monotone — the problem is solved; all that remains is the feasibility subroutine.

★★ · The Sawmill

Trees of heights 20, 15, 10, 17. A blade set at height H cuts off everything above H, collecting Σ max(0, hᵢ − H) units of wood. Find the largest integer H that collects at least 7 units. (A classic from the training sites, known there as EKO.)

Pause. Don't optimize. Guess and check — efficiently.

Solution. Feasibility f(H) = "wood(H) ≥ 7". Wood is non-increasing in H, so f is monotone: true low, false high. Binary search on [0, 20]:

• H = 10: wood = 10 + 5 + 0 + 7 = 22 ≥ 7 ✓ → go higher, [10, 20]
• H = 15: wood = 5 + 0 + 0 + 2 = 7 ≥ 7 ✓ → [15, 20]
• H = 18: wood = 2 + 0 + 0 + 0 = 2 ✗ → [15, 17]
• H = 16: wood = 4 + 0 + 0 + 1 = 5 ✗ → [15, 15]

Answer H = 15 (wood(15) = 7 ✓, wood(16) = 5 ✗). Five decision calls replace a scan of all heights; with heights up to 10⁹ it is about thirty calls. The logarithm is the whole business model. ∎

The Move — Interrogate candidates, not the optimum. If a whispered answer would be easy to check, stop trying to compute it and start bisecting for it.

★★★★ · Aggressive Cows

Stalls at positions 1, 2, 4, 8, 9 on a line. Place 3 cows in stalls so that the minimum distance between any two is as large as possible. (The classic is known as AGGRCOW.)

Pause here. Two tools will have to compose.

Solution. Decision version: can 3 cows be placed with every pair at least d apart? Check greedily: put the first cow in the leftmost stall, then always take the next stall at least d beyond the last cow; count placements. The check needs its own small exchange proof: if any valid placement of k cows at gap d exists, sliding its leftmost cow to the leftmost stall and each next cow to the earliest stall ≥ d beyond the previous only moves cows leftward or not at all, never violating d — so the leftmost-greedy placement seats at least as many cows. Hence "greedy seats ≥ 3" is equivalent to feasibility. Feasibility is monotone — bigger d is harder — so binary search d on [1, 8]:

• d = 4: place at 1 → next ≥ 5 → 8 → next ≥ 12 → none. Two cows < 3 ✗ → [1, 3]
• d = 2: 1 → 4 → 8. Three cows ✓ → [2, 3]
• d = 3: 1 → 4 → 8, gaps 3 and 4. Three cows ✓ → [3, 3]

Answer d = 3, with d = 4 shown infeasible. ∎

The ★★★★ content is the frame: the solver never optimized anything. "Maximize the minimum" dissolved into (a) spotting monotonicity, (b) a greedy decision check carrying its own exchange proof, (c) logarithmically many repetitions. Tools composing tools — this section outside, the previous one inside.

The Move — Dissolve "maximize the minimum" into feasibility. The optimum is a threshold; hunt the threshold, not the solution.

Machines and this move. Fully mechanical once monotonicity is asserted — this may be the single most common pattern in models' competitive-programming training data; the human step is certifying monotonicity on messy problems, where "obviously monotone" occasionally isn't. Prove the one-line implication before trusting the search.

Working Backwards

The tool. Start from the goal state and compute predecessors, instead of exploring forward from the start. In games this is backward induction: label terminal positions Won or Lost, then propagate — a position is Winning if some move reaches a position Lost for the opponent, Losing if all moves reach Winning ones. In puzzles it is "what must the last step have been?" — the last step is often far more constrained than the first, so the tree is thinner from that end.

The smell. A clearly specified goal with a foggy start: "reach exactly 100," "end with one token," "mate in three." Games of perfect information — "who wins with best play?" Moves easier to invert than to choose. The reflex: when forward branching is wide and the goal is narrow, grow the tree from the narrow end — or from both ends at once, halving the exponent.

★★ · The Race to 100

Two classics, one skeleton. (a) 21 stones; players alternately remove 1, 2, or 3; whoever takes the last stone wins. (b) Players alternately add 1 through 10 to a running total starting at 0; whoever says 100 wins. Who wins each, and how?

Pause. Start from the end — literally.

Solution. (a) Label backwards. Facing 0 stones, you have lost — the previous player took the last. Facing 1–3, you win (take them all). Facing 4, every move hands the opponent a win: 4 is Losing. Propagating, the Losing positions are exactly the multiples of 4 — from 4k any take of t leaves a non-multiple; from 4k + r (r = 1, 2, 3), take r. Since 21 ≡ 1 (mod 4), the first player wins: take 1, then answer every t with 4 − t, restoring a multiple of 4. (b) The same engine, additive: the targets to hand your opponent run backwards from 100 in steps of 11 — 100, 89, 78, …, 12, 1 — since your k is answered by 11 − k. The first player says 1, then climbs 12, 23, …, 89, 100. ∎

Forward play at 21 sees a bushy tree; backward labeling yields the entire theory as one arithmetic progression. It also plants the general concept — cold positions (Losing for the mover) versus hot — the periodic skeleton under Nim-like game theory: Chapter 9's balanced columns were exactly Nim's cold positions, and the general theory (Sprague–Grundy) grows from this seed.

The Move — Label from the end. The goal is one state; the start is many. Compute Won/Lost outward from the goal and read the answer off your own table.

★★★★ · Wythoff's Game, and the Golden Ratio

Two piles of stones. A move: take any positive number from one pile, or take the same positive number from both. Last stone wins. Characterize the losing positions.

Pause here. Grind small cases before you theorize.

Solution. Backward-label small states, pairs unordered. (0,0) is Losing — the mover faces no stones, the previous player took the last. Everything that reaches (0,0) in one move — every (k,0) and (k,k) — is Winning. Scan upward for the next all-exits-Winning state: (1,2). Its moves reach (0,2), (1,1), (1,0), and diagonally (0,1) — each Winning (each reaches (0,0) in one). So (1,2) is Losing. Prune everything that can reach (0,0) or (1,2), and the next candidate is (3,5). Its single-pile moves reach (0,5), (1,5), (2,5), (3,4), (3,3), (3,2), (3,1), (3,0); its diagonal moves reach (2,4), (1,3), (0,2). Every one is Winning: (0,5), (3,0), (0,2) hit (0,0) directly and (3,3) does diagonally; (1,5) → (1,2) by taking 3; (2,5) → (2,1) by taking 4; (3,2) → (1,2) by taking 2; (1,3) → (1,2) by taking 1; (3,1) → (2,1) by taking 1; (3,4) → (1,2) by the diagonal −2; (2,4) → (2,1) by taking 3. (Pairs are unordered: (2,1) is (1,2).) So (3,5) is Losing. The sieve continues: (0,0), (1,2), (3,5), (4,7), (6,10), (8,13), …

Two structural facts fall out of the table: every positive integer appears in exactly one Losing pair, and the k-th pair differs by exactly k. Closed form (Wythoff, 1907): the k-th losing position is (⌊kφ⌋, ⌊kφ²⌋), with φ = (1 + √5)/2. Check — k = 1: (1, 2); k = 2: (⌊3.236⌋, ⌊5.236⌋) = (3, 5); k = 3: (⌊4.854⌋, ⌊7.854⌋) = (4, 7) ✓. Why the golden ratio: Beatty's theorem says the sequences ⌊kα⌋ and ⌊kβ⌋ partition the positive integers exactly when 1/α + 1/β = 1 — and 1/φ + 1/φ² = 1; while φ² = φ + 1 makes the k-th gap exactly k. Those two properties are precisely the sieve's rules: each new Losing pair uses the smallest unused integer (the partition property) with gap k (the diagonal-move property). ∎

Retrograde analysis was the experiment; the golden ratio is the theory. The honest workflow — grind the backward table, stare, conjecture, then prove via Beatty — is exactly how the result was found, and it models a two-stroke engine this book keeps meeting: machinery generates data; recognition compresses it; proof certifies it.

The Move — Grind the table, then earn the formula. Backward induction gives you truth without insight; compressing the table into a closed form is the insight — and it must then be proved, not pattern-matched.

Machines and this move. Retrograde analysis is the machine's home turf — chess endgame tablebases, every position of seven pieces or fewer solved backward, are its industrial monument; the human stroke is compressing the table into φ, which no tablebase will ever volunteer.

The five, at a glance

Builders, all five: each returns not just an answer but a construction with a warranty. One family remains — the tools that change what a problem is before anyone starts solving it.