The Modeler's Eye

The last family does not attack a problem; it changes what the problem is. Re-representation — story into graph, sum into set, puzzle into average — is the quietest move in the arsenal and the most powerful: after the right translation, famously hard problems finish themselves. It is also where human solvers hold their widest lead over machines. The chapter ends with three famous set pieces, told with the record straightened.

Story → Structure

The tool. Recast the problem as an instance of a known, solved abstraction: a graph, a flow network, a matching, a shortest path, a system of congruences. The solving act is a translation — say what the vertices are, what the edges are, and which classical theorem now applies. Competitive programming at the top level is a reduction-recognition sport; most hard problems are a known kernel wearing a costume.

The smell. Entities with pairwise relationships: a graph is coming. "Assign X to Y" under compatibility constraints: bipartite matching. "Throughput," "bottleneck," "cut them off": max-flow, min-cut. Sequential states with legal transitions: shortest path over a state space, not a physical space. The meta-signal: the story resists direct attack, yet every sentence sounds like it is describing a structure. The reflex: name the vertex.

The book's first puzzle was secretly this section's easy example. Chapter 1's wolf, goat, and cabbage becomes: vertex = a legal distribution of {farmer, wolf, goat, cabbage} over two banks — 16 raw states, 10 legal; edge = one crossing. The question is now a shortest path; breadth-first search finds the 7-crossing route, certifies it minimal — and the famous aha, bringing the goat back, becomes just an edge like any other, crossed by the same dumb search. The insight was in the modeling; after it, no insight is required. The same move solves Rubik's cube, sliding puzzles, and protocol verification: shortest paths in graphs of configurations, not places.

★★★★ · Guards in the Palace

A 4 × 4 palace floor has treasures at cells (1,1), (1,3), (2,2), (3,1), (3,3) — row, column. A guard patrols one full row or one full column. Find the minimum number of guards covering all treasures, and prove it minimal.

Pause here. What, precisely, is a vertex?

Solution. Go bipartite: left vertices are rows, right vertices are columns, and each treasure is an edge joining its row to its column. A guard is a vertex; covering all treasures means touching every edge: a vertex cover. In bipartite graphs, minimum vertex cover equals maximum matching — König's theorem, 1931. Lower bound: treasures (1,1), (2,2), (3,3) form a matching of size 3, sharing no row and no column, and any guard covers at most one edge of a matching — so 3 guards are forced. Upper bound: rows 1, 2, 3 cover all five treasures. Minimum: 3. ∎ (Direct check that two fail: covering (2,2) takes row 2 or column 2, which touches none of the four corner treasures — and one line covers at most two of those four.)

Nothing in the story says "graph," and the winning translation — treasure = edge, not vertex — is exactly what modeling skill consists of. Once made, a 1931 theorem finishes the fight, certificate included: the matching is the lower-bound witness.

The Move — Name the vertex. Get the atoms right and the theorem is usually waiting.

Machines and this move. Executing a max-flow is trivial; deciding the story is a flow problem is abduction over an open representation space — models recognize costumes they have read and fail on fresh disguises.

Casework & WLOG

The tool. When no single argument covers everything, partition the space into finitely many cases and kill each. The discipline: exhaustive (say why), preferably disjoint, and few — which is where "without loss of generality" earns its keep: quotient out symmetry before splitting, by fixing an ordering, a position, a naming.

The smell. A small structured space — two colors, residues mod 3, who moves first. A statement invariant under relabeling: that invariance is a coupon; spend it. Warning smell in the other direction: a case count past five or so usually means a missing invariant or extremal choice. Casework is the honorable last resort.

★★ · The Party of Six

Prove that among any 6 people, some 3 mutually know each other or some 3 are mutual strangers.

Pause. Fix one guest and look at their five relationships.

Solution. Fix a person v. Of the 5 relations at v, some kind appears at least ⌈5/2⌉ = 3 times (pigeonhole); WLOG it is "know" — the statement is symmetric under swapping know/stranger, so this halves the proof. Say v knows A, B, C. If some pair of them know each other, that pair plus v is a knowing triangle. If no pair does, A, B, C are three mutual strangers. Done either way. ∎ Sharpness: seat 5 people in a pentagon, neighbors acquainted, diagonals strangers — no triangle of either kind. So 6 is exact: R(3,3) = 6.

Three tools in eight lines — pigeonhole picks the branch, WLOG halves the tree, excluded middle makes the cases exhaustive. Ramsey theory's slogan follows: structure becomes unavoidable at scale.

The Move — Quotient the symmetry before you split. Every symmetry you fail to spend becomes two identical cases written out twice.

★★★★ · Three of Five

Prove that among any 5 integers, some 3 have a sum divisible by 3 — and show that 4 integers do not suffice.

Pause here. Choose the case split so each branch has a weapon.

Solution. Only residues mod 3 matter; sort the five into classes R₀, R₁, R₂ and split on the maximum class size. Case A — some class holds ≥ 3. Take three from it: sum ≡ 3r ≡ 0 (mod 3). Case B — every class holds ≤ 2. Five numbers then force sizes (2, 2, 1) in some order — in particular no class is empty, since two classes hold at most 4. One number from each class: 0 + 1 + 2 ≡ 0 (mod 3). The cases are exhaustive: the maximum is either ≥ 3 or ≤ 2. ∎ Sharpness. Four integers dodge: residues {0, 0, 1, 1} — any three sum to 1 or 2 (mod 3), never 0. So 5 is exact. This is the n = 3 case of Erdős–Ginzburg–Ziv (1961): among any 2n − 1 integers, some n sum divisibly by n, and 2n − 2 never suffice — n − 1 zeros and n − 1 ones being the general dodge. Chapter 8's "strange exactness" signpost, detonating on schedule.

The Move — Design cases backward from the finishing moves. Split on a variable chosen so every branch dies to an available weapon; an analysis that cannot exhibit tightness is often hiding a slack case.

Machines and this move. Exhaustive checking is the machine's native gait — Appel and Haken's four-color proof (1976) checked about 1,936 configurations — but the WLOG license, seeing which quotient collapses 3⁶ cases to 2, remains a human design act.

Solve Smaller First

The tool. Two directions of one dial. Small cases first: compute n = 1, 2, 3, 4 by hand, conjecture the pattern, then prove it — the computed cases become the induction's base. Generalize first — Pólya's inventor's paradox again: replace the specific question (100, this year's number, this board) with its parameterized family; the general question has more structure to grab, and the specific answer falls out by substitution.

The smell. A specific large constant — 2026, 100, 10¹⁸ — is almost always a costume over a clean parameter n. "Find the value" with no visible structure: tabulate immediately. A statement that feels arbitrary: generalize until it feels inevitable. And the professional's reflex: a pattern from three data points is a hypothesis, not an answer.

★★ · The Last Digit of 7²⁰²⁶

Find the last digit of 7²⁰²⁶.

Pause. Replace 2026 with n and make a small table.

Solution. Tabulate 7ⁿ mod 10: 7, 9, 3, 1, then 7, 9, 3, 1, … — period 4. (Once a residue repeats, the whole cycle must: multiplication by 7 mod 10 is a fixed map.) So the answer depends only on n mod 4, and 2026 ≡ 2 (mod 4): last digit = 7² mod 10 = 9. ∎ Behind the toy, a general machine: powers mod m are eventually periodic — pigeonhole on m residues — and Euler's theorem predicts the period divides φ(10) = 4.

The Move — Replace the year with n. A two-line periodicity in a four-digit costume. Undress it.

★★★★ · Circles Against the Siren

n circles in the plane, each pair meeting in exactly 2 points, no three through a common point. Into how many regions do they cut the plane? Compute small cases, conjecture — then prove.

Pause here, and do not trust your first formula.

Solution. Small cases: n = 1 → 2 regions; n = 2 → 4; n = 3 → 8. The siren sings: 2ⁿ. Test n = 4. The fourth circle crosses the 3 others in 6 points, is cut into 6 arcs, and each arc splits one region: 8 + 6 = 14, not 16. The doubling was a mirage of small numbers. The incremental count, now honest: the k-th circle meets its k − 1 predecessors in 2(k − 1) points, is cut into 2(k − 1) arcs, and each arc splits exactly one existing region — adding 2(k − 1), while the first circle adds 1 to the initial 1. R(n) = 2 + Σₖ₌₂ⁿ 2(k − 1) = n² − n + 2. Check: 2, 4, 8, 14, 22 ✓. Then certify independently with Euler's formula V − E + F = 2: V = n(n − 1) intersection points; each circle carries 2(n − 1) of them, so E = 2n(n − 1) arcs; F = 2 − V + E = n(n − 1) + 2 — the same n² − n + 2. ∎ Two roads, one answer: the actual standard of "verified."

Keep the cautionary twin beside it — Moser's circle problem: n points on a circle, all chords drawn, no three concurrent; count regions. The sequence runs 1, 2, 4, 8, 16 — then 31 at n = 6. The true formula is C(n,4) + C(n,2) + 1 (each chord adds a region; each interior crossing, one per 4 points, adds one more): 1, 2, 4, 8, 16, 31, 57 — A000127 in the OEIS. Five consecutive doublings, then betrayal. Small cases propose; only proofs dispose.

The Move — Conjecture cheaply, verify expensively, certify twice. The fourth small case is cheap insurance; a second independent derivation is the seal.

Machines and this move. Machines out-enumerate us absurdly — competitors really do compute four terms and consult the OEIS — but extrapolating 2ⁿ from four terms is Moser's trap industrialized; conjecture-then-certify transfers verbatim to auditing machine output.

Counting Twice

The tool. Count one set of objects by two different bookkeeping schemes; both count the same thing, so the two expressions are equal — and that equation is the theorem. The usual object is a set of incidences: the row sums versus the column sums of one 0/1 matrix. Double counting is combinatorics' identity-forge.

The smell. An identity or divisibility between count-like quantities; a sum that would simplify reindexed — "for each student…" versus "for each problem…"; handshakes, memberships, averages (an average is a double count divided by a headcount). The reflex: define the incidence set explicitly — "pairs (x, y) such that…" — then total it both ways.

★★ · Handshakes, and a Census

(a) Prove that in any graph the degrees sum to twice the number of edges, and conclude that the number of odd-degree vertices is always even. (b) In a class, 35 students each solved exactly 3 problems, and every problem was solved by exactly 5 students. How many problems?

Pause. Both are the same move.

Solution. (a) Count the incidences (v, e) with vertex v an endpoint of edge e: grouped by vertex, Σ deg(v); grouped by edge, exactly 2 each. So Σ deg(v) = 2|E| — and a sum of integers that is even must contain an even number of odd terms, so odd-degree vertices come in even supply. (b) Count (student, problem) incidences twice: 35 · 3 = P · 5, so P = 21. ∎ No enumeration, no structure — two viewpoints alone pin the answer.

The Move — Total the matrix both ways. Rows or columns, the grand total cannot care. Make that indifference say something.

★★★★ · Every Fixed Point, Counted Sideways

(IMO 1987, Problem 1.) Let pₙ(k) be the number of permutations of {1, …, n} with exactly k fixed points. Prove that Σₖ₌₀ⁿ k · pₙ(k) = n!.

Pause here. What single set might both sides be counting?

Solution. The left side counts each permutation π once per fixed point it has: it is the size of the incidence set F = {(π, i) : π(i) = i}, grouped by π. Group by i instead: the permutations fixing a given i are exactly the permutations of the other n − 1 elements — (n − 1)! of them. So |F| = n · (n − 1)! = n!. ∎ Sanity at n = 3: one permutation has 3 fixed points, three have 1, two have 0; 3·1 + 1·3 + 0·2 = 6 = 3! ✓.

An IMO problem — and the entire solution is one change of viewpoint, three lines long. Difficulty and length-of-best-solution are nearly independent variables; the exam tested whether that sum smells like an incidence count. Read probabilistically, the identity says the average permutation has exactly one fixed point — which hands us the next tool.

The Move — Every sum is a set being counted; find the set.

Machines and this move. Verifying that two counts agree is arithmetic; choosing the incidence set is a re-representation act that generalizes poorly in models on novel weighted sums.

The Probabilistic Lens

The tool. Import probability into problems that mention none. Engine one — linearity of expectation: E[X₁ + ⋯ + Xₙ] = Σ E[Xᵢ] with zero independence assumptions, so tangled, correlated messes decompose into per-part sums. Engine two — averaging, Erdős's probabilistic method: if the average over a family is v, some member achieves at least v. Pick a random object, compute its expected merit, and a good object exists — never constructed.

The smell. "Prove there exists an arrangement / coloring / subset with at least…" and no visible construction: randomize and average. Any quantity that is a sum of many small overlapping contributions: indicator sums. The reflex: name the indicators — and watch dependence, the great obstacle everywhere else, simply not matter.

★★ · The Average Permutation

Show that the average number of fixed points of a random permutation of n elements is 1 — for every n.

Pause. No sums over k allowed.

Solution. Let Xᵢ = 1 if π(i) = i, else 0; the number of fixed points is X = Σ Xᵢ, and E[Xᵢ] = P(π(i) = i) = (n − 1)!/n! = 1/n. Linearity — the Xᵢ are heavily correlated, and it does not matter: E[X] = n · (1/n) = 1. ∎

The arithmetic is the IMO identity from one section back, divided by n!. But the double count needed an inspiration — find the incidence set — while the expectation needed only a standing reflex. Probabilistic language converts one-off insights into routine calculations; that conversion is the point of owning a lens.

The Move — Write the indicators. Linearity never asks whether they are independent.

★★★★ · The Big Cut

Prove that every graph with m edges has a partition of its vertices into two sides with at least m/2 edges crossing between them. (No randomness in the statement.)

Pause here. Flip a coin for every vertex.

Solution. Color each vertex Left or Right by independent fair coin. For an edge e = {u, v}, let Xₑ indicate "u and v on opposite sides": P(Xₑ = 1) = 1/2, so E[Σ Xₑ] = m/2. An average of m/2 forces some outcome ≥ m/2 — an average cannot exceed its maximum. That outcome is the partition. ∎

Then derandomize, with an old friend. The proof names no cut, but a monovariant (Chapter 9) extracts one: start anywhere; while some vertex has more neighbors on its own side than across, flip it. Each flip strictly increases the crossing count, which is bounded by m, so the process halts — and at a halt every vertex has at least half its degree crossing, so crossings ≥ ½ · Σ deg(v)/2 = m/2. Local search finds what probability promised. (One rung up: a random assignment satisfies 7/8 of any 3-SAT formula's clauses, each failing with probability 1/8 — and Håstad proved 7/8 optimal to approximate unless P = NP. The trivial random bound is the exact frontier of tractability.)

Erdős founded the method in 1947, lower-bounding Ramsey numbers with random colorings. It is average-case thinking as a weapon: ask what a typical case achieves, then upgrade typicality to existence (averaging) or to an algorithm (derandomization). Chapter 7's hundred-prisoner miracle is this lens at full power — no individual's odds improve; the strategy merely herds the failures into the same unlucky worlds. The mean is untouchable; the variance is the lever.

The Move — Upgrade the average to existence, then to an algorithm.

Machines and this move. There is nothing for a search to find until someone reframes "exists" as "average" — owning the decision to randomize a deterministic world is still the human part.

Budget First

The tool. Before solving, budget: the size of the search space, the information content of the answer, the operations affordable — and let those numbers choose the method. For programmers it is literal: about 10⁸ simple operations per second, so the constraints encode the intended algorithm. For mathematicians it is information-theoretic: a procedure with k ternary outcomes distinguishes at most 3ᵏ situations, so any strategy needs ⌈log(#cases)⌉ steps — a lower bound requiring no cleverness, only counting.

The competitive programmer's decoder ring, worth printing:

Read forward, the table budgets your plan; read backward, it is Chapter 8's decoder of authorial intent.

The smell. Any stated constraint — n ≤ 20, n ≤ 10⁵, and n ≤ 10¹⁸ are three different problems wearing one statement. "At least how many questions / weighings / comparisons?": an information bound begs to be counted. A plan whose cost is unestimated: estimate before executing.

★★ · Meet in the Middle

How many subsets of {1, 2, 3, 4} sum to 5 — and how would you count subset-sums among 40 numbers, where brute force over 2⁴⁰ ≈ 10¹² subsets is dead?

Pause. Split the problem, not the difference.

Solution. Halve: L = {1, 2}, R = {3, 4}, with subset sums {0, 1, 2, 3} and {0, 3, 4, 7}. A full subset is a pair, one part from each side, and it hits 5 when sₗ + sᵣ = 5: the pairs (1, 4) = {1} + {4} and (2, 3) = {2} + {3}. Two subsets, matching direct enumeration. For n = 40: enumerate each half's 2²⁰ ≈ 10⁶ sums, sort one side, binary-search the complements — about 2²⁰ · 20 operations. Seconds instead of centuries. The only idea is arithmetic: 2ⁿ is lethal, 2 · 2^(n/2) is cheap, and pairs of half-subsets biject with subsets. Budget arithmetic did not check the method — it invented it. ∎

The Move — Buy half the exponent. When 2ⁿ kills you, ask whether the problem splits into halves that meet at a seam.

The information-theoretic face already won a battle in Chapter 7: the twelve-ball weighing had 24 possible answers and a three-outcome scale — 3² = 9 < 24, so two weighings are dead; 3³ = 27 just clears. And the bound did double duty, designing the scheme: each weighing must split the survivors into near-equal thirds, hence four against four, while six against six wastes the balanced outcome. Count the answer space, count the channel capacity, let the ratio steer — the same reflex prices twenty questions (2²⁰ ≈ 10⁶ objects), comparison sorting (log₂ n! ≈ n log n), and, read backward, the setter's constraints.

Machines and this move. Asymptotics are the machine's element, yet the pre-computation estimate is a planning behavior automated agents notoriously skip — and the information bound is a proof about all strategies, not a strategy: that nonconstructive flavor again.

Three Set Pieces

Three famous stories, each a tool in its best-known costume — and each with a correction the retellings usually skip.

★★ · The Seven Bridges of Königsberg

Königsberg, 1736 — now Kaliningrad. The river Pregel divides the city into four land masses — the island of Kneiphof, the north bank, the south bank, the eastern spit — joined by seven bridges. Can a stroll cross every bridge exactly once?

Pause. You have the tool now: name the vertex.

Solution. Euler's move — arguably the founding act of graph theory and of topology, "the geometry of position" in his phrase — was to delete the city: each land mass a dot, each bridge a line. Only the incidence structure survives. Then the observation: a walk passing through a vertex consumes its bridges in pairs, one in and one out, so every land mass except possibly the start and the end needs an even number of bridges. Königsberg's degrees are 5, 3, 3, 3 — summing to 14 = 2 × 7 bridges, the handshake lemma's quiet sanity check — four odd vertices, where a walk tolerates at most two. No such stroll exists. ∎ Euler proved the impossibility direction; that at most two odd vertices suffices on a connected multigraph was nailed down by Hierholzer in 1873.

The moral is this chapter's opening move in miniature: the insight was not about bridges. It was the decision that only structure matters — one abstraction, then parity a child can check.

The Move — Delete the city. Strip every feature the question does not consume; what remains is usually a solved problem.

★★★ · The Circle of Josephus

The legend: Yodfat, 67 CE — the historian Flavius Josephus, trapped with his soldiers, survives a death circle. Honesty first: his own account (The Jewish War, book 3) says lots were drawn, and that he remained at the end "by chance or by providence." The deterministic version — n people in a circle, count around, every k-th falls, the last one lives — is the later mathematicians' formalization. Where should you stand?

Pause. Solve the two-person circle, then the three.

Solution. Let J(n) be the survivor's position, 0-indexed, with step k. After the first elimination (position k − 1), the remaining n − 1 people play the same game shifted by k: J(n) = (J(n−1) + k) mod n, with J(1) = 0. One line, O(n) to run. Verified by simulation for k = 2: n = 5 eliminates 2, 4, 1, 5, leaving 3, and the recurrence gives 0, 0, 2, 0, 2 → position 3 ✓; n = 6 eliminates 2, 4, 6, 3, 1, leaving 5, and the recurrence gives 4 → position 5 ✓. For k = 2 there is a closed form: write n = 2^m + L with 0 ≤ L < 2^m; the survivor, 1-indexed, is 2L + 1. Equivalently — a jewel — rotate n's binary representation left by one bit: 41 = 101001₂ → 010011₂ = 19, and indeed 41 = 32 + 9 gives 2·9 + 1 = 19 ✓; 6 = 110₂ → 101₂ = 5 ✓. (The first pass eliminates the evens, and the survivors relabel as exactly a binary shift — recursion made visible in the radix.) The legend's numbers: with n = 41 and k = 3, the recurrence run in full gives J(41) = 30 — position 31, counting from 1, with the second-to-last survivor at 16. The traditional telling, Josephus at place 31 and a companion at 16, is arithmetically exact — whether the historian computed or improvised. ∎

The Move — Shrink the circle. One elimination turns the game into a smaller copy of itself, relabeled; solve the smallest and lift the answer back.

★ · The Schoolmaster's Sum

The story: Büttner the schoolmaster sets his class to summing 1 + 2 + ⋯ + 100, expecting a quiet hour; little Gauss writes 5050 on his slate almost immediately. How — and did it happen?

Pause. You met the move in Chapter 9.

Solution. Pair first with last: 1 + 100, 2 + 99, …, 50 + 51 — fifty pairs, each totaling 101: 50 × 101 = 5050. The robust general form dodges any worry about odd n: write the sum forwards and backwards and add columnwise — 2S = n(n + 1), so S = n(n + 1)/2. ∎ Now the record: the anecdote's earliest source, Sartorius von Waltershausen's memorial biography of Gauss (1856), mentions an arithmetic-series task but names neither 1-to-100 nor the pairing trick; the vivid details accreted over a century of retellings, and Brian Hayes (American Scientist, 2006) traced dozens of mutually contradictory versions. Tell it as legend; teach it as mathematics. The real content is the involution k ↦ n + 1 − k that makes every pair constant — bedrock that sums any arithmetic series and shows C(n, k) = C(n, n−k).

The Move — Pair to a constant. Chapter 9's symmetry tool in its Sunday clothes.

The library, complete

Sixteen tools across three chapters — boxes invented, charges conserved, extremes interrogated, mirrors held, colorings engineered; hypotheses strengthened, histories compressed, optima morphed, thresholds bisected, tables run backward; vertices named, symmetries quotiented, years turned into n, sums counted sideways, worlds averaged, budgets read. Every volume in this library is a way of seeing, not of grinding. The machines have read the library too — they have read everything. Where they now execute it faster than any human, and where they still cannot reach for it unprompted, is the next Part's question. It comes with dates and numbers.