Competition mathematics and problem solving

Case analysis and extremal principle

Solving problems by splitting into exhaustive cases, or by examining an extreme (largest/smallest) element.

IntuitionSplitting an impossible-looking problem into cases you can handle

Imagine a round-robin chess tournament with $5$ players, no draws allowed: every pair plays exactly once, and one player always wins. Can the players always be lined up in some order $v_1, v_2, \dots, v_5$ so that each one beat the very next player in line? Checking all $5! = 120$ orderings by hand is wasteful, and the answer may look like it depends on who beat whom. Instead, pick out the single longest winning chain that already exists among the players — the most extreme chain — and a short argument shows it cannot be improved, which forces it to already include everyone.

A tournament graph on

5

players: each arrow points from winner to loser. The highlighted path is a longest existing winning chain; the extremal principle shows it must already visit every player.

UndergraduateTwo complementary strategies: exhaustive case split and the extremal principle

Definition: Exhaustive case analysis and the extremal principle

Exhaustive case analysis partitions the set of all possibilities $S$ into finitely many pairwise-disjoint cases $S_1,\dots,S_k$ whose union is all of $S$ , then verifies the claim separately inside each case; because no possibility is left out and none is double-counted, proving the claim in every case proves it for $S$ . The extremal principle instead looks at a single most extreme member of a finite (or well-ordered) collection — the largest, the smallest, the longest — with respect to some quantity, and exploits the fact that this element cannot be improved upon to derive a contradiction or a direct construction.

S = S_1 \cup S_2 \cup \cdots \cup S_k,\quad S_i \cap S_j = \varnothing \text{ for } i \neq j

Here $S$ is the entire universe of possibilities under consideration, $k$ is the number of cases, and the two conditions say the cases are exhaustive (their union recovers $S$ , so nothing is missed) and mutually exclusive (their pairwise intersections are empty, so nothing is counted twice).

\varnothing \neq A \subseteq \mathbb{Z}_{\ge 0} \implies \exists\, m \in A \text{ with } m \le a \text{ for all } a \in A

This well-ordering principle is what makes the extremal principle rigorous on integers: any nonempty set $A$ of nonnegative integers has a least element $m$ , so 'the smallest counterexample' or 'the shortest path' is never a vacuous phrase — it is guaranteed to exist, and by symmetry the same holds for a maximum whenever $A$ is additionally finite or bounded above.

M = \max_{x \in A} f(x) \implies f(x) \le M \text{ for every } x \in A

This says nothing more than the definition of a maximum — but it is the engine of every extremal-principle proof: once $M$ is fixed as the maximum, every competitor $x$ must satisfy $f(x) \le M$ , including cleverly constructed competitors that the proof builds specifically to expose a contradiction if $M$ were not already extreme enough.

Case analysis and the extremal principle side by side
Technique	Core idea	Typical use
Exhaustive case split	Partition all possibilities into finitely many disjoint cases and verify each one	Parity/remainder arguments modulo $n$ , small finite enumeration
Extremal principle (maximum)	Take the element maximizing some quantity and show it cannot be strictly improved	Longest path in a graph, farthest pair of points, largest counterexample
Extremal principle (minimum)	Take the element minimizing some quantity and show it cannot be strictly beaten	Nearest point–line distance (Sylvester–Gallai), smallest counterexample (infinite descent)
Well-ordering of $\mathbb{Z}_{\ge 0}$	Guarantees a minimum exists in any nonempty set of nonnegative integers	Makes 'the extremal element' rigorous; foundation of infinite descent

UndergraduateKey theorems: an ordinary line via minimum distance, and Hamiltonian paths in tournaments

Theorem: Sylvester–Gallai theorem (Kelly's minimum-distance proof)

If $n \ge 3$ points in the plane are not all collinear, then there exists a line passing through exactly $2$ of the points (an ordinary line).

Why is it true?

Among the finitely many pairs (point, line-through-two-points) where the point does not lie on the line, pick the pair achieving the strictly smallest distance; if that closest line had a third point on it, geometry would produce an even closer pair, which is impossible by minimality.

Proof

Step 1 (set up the extremal choice). Let $P$ be the given finite set of $n \ge 3$ points, not all collinear. Consider the finite set of pairs $(Q, \ell)$ where $\ell$ is a line through at least $2$ points of $P$ and $Q \in P$ is a point not on $\ell$ . This set is nonempty (since $P$ is not all collinear) and finite, so by the extremal principle we may choose a pair $(Q_0, \ell_0)$ minimizing the distance $d(Q_0, \ell_0)$ from the point to the line.

Step 2 (assume a contradiction). Suppose, for contradiction, that $\ell_0$ contains at least $3$ points of $P$ . Let $F$ be the foot of the perpendicular from $Q_0$ to $\ell_0$ . Since there are $\ge 3$ points of $P$ on $\ell_0$ and they lie on at most $2$ rays emanating from $F$ along $\ell_0$ , the pigeonhole principle gives two of them, $B$ and $C$ , on the same ray, with $B$ between $F$ and $C$ (allowing $B = F$ ).

Step 3 (build a closer pair via similar triangles). Drop a perpendicular from $B$ to the line $Q_0C$ , with foot $G$ . The right triangles $\triangle BGC$ and $\triangle Q_0FC$ share the angle at $C$ , so they are similar, giving $\dfrac{BG}{Q_0F} = \dfrac{BC}{Q_0C}$ . Since $B$ lies between $F$ and $C$ we have $BC \le FC$ , and since $\triangle Q_0FC$ has a right angle at $F$ , the hypotenuse satisfies $FC < Q_0C$ ; combining these, $BC < Q_0C$ , hence $BG < Q_0F = d(Q_0, \ell_0)$ .

Step 4 (contradiction). The line $Q_0C$ passes through $2$ points of $P$ (namely $Q_0$ and $C$ ), and $B$ is a point of $P$ not on it, so $(B, Q_0C)$ is a valid pair in our finite set with $d(B, Q_0C) = BG < d(Q_0, \ell_0)$ , contradicting the minimality of $(Q_0, \ell_0)$ .

Step 5 (conclusion). The contradiction shows $\ell_0$ cannot contain $3$ or more points of $P$ ; since it was chosen to contain at least $2$ , it contains exactly $2$ , so $\ell_0$ is the required ordinary line.

Theorem: Every tournament has a Hamiltonian path (Rédei's theorem)

In every tournament on $n$ vertices (a complete directed graph where, for each pair of distinct vertices $u, v$ , exactly one of the arcs $u \to v$ or $v \to u$ is present), there exists a Hamiltonian path $v_1 \to v_2 \to \cdots \to v_n$ visiting every vertex exactly once.

Why is it true?

Take a directed path of maximum length; if some vertex were left out, the tournament property (every pair has a directed edge) would let us either extend the path at one end or insert the missing vertex in the middle, contradicting maximality.

Proof

Step 1 (extremal choice). Among all directed paths in the tournament, choose one, $P: v_1 \to v_2 \to \cdots \to v_k$ , with the largest possible number of vertices $k$ ; such a maximum exists because there are only finitely many vertices. Suppose, for contradiction, that $k < n$ , and let $u$ be a vertex not on $P$ .

Step 2 (case split at the two ends). Since the tournament has exactly one of $u \to v_1$ or $v_1 \to u$ : if $u \to v_1$ held, prepending $u$ would give the longer path $u \to v_1 \to \cdots \to v_k$ , contradicting the maximality of $k$ ; hence $v_1 \to u$ holds. Symmetrically, exactly one of $v_k \to u$ or $u \to v_k$ holds: if $v_k \to u$ held, appending $u$ would give a longer path, contradicting maximality; hence $u \to v_k$ holds.

Step 3 (locate an insertion point). We now know $v_1 \to u$ and $u \to v_k$ . Let $j$ be the largest index in $\{1, \dots, k-1\}$ such that $v_j \to u$ holds; this set of indices is nonempty since $j = 1$ works, so by the extremal principle $j$ exists. By maximality of $j$ , the arc $v_{j+1} \to u$ does not hold, so the tournament property forces $u \to v_{j+1}$ .

Step 4 (contradiction by insertion). Combining $v_j \to u$ with $u \to v_{j+1}$ , we insert $u$ between $v_j$ and $v_{j+1}$ to form the path $v_1 \to \cdots \to v_j \to u \to v_{j+1} \to \cdots \to v_k$ , which has $k + 1$ vertices, contradicting the maximality of $k$ .

Step 5 (conclusion). No such vertex $u$ can exist, so $k = n$ and $P$ is a Hamiltonian path.

AdvancedReal-World Applications and Worked Examples

In sports analytics and ranking algorithms, Rédei's theorem guarantees that the results of any round-robin tournament — even a cyclic upset like $A$ beats $B$ , $B$ beats $C$ , $C$ beats $A$ — can always be arranged into at least one linear ranking where each competitor beats the next, which is exactly the ordering produced by 'insert the odd one out' scheduling heuristics. In algebraic complexity theory, quantitative versions of the Sylvester–Gallai theorem bound how many linear forms can pairwise satisfy restrictive collinearity conditions, and are a key tool for proving lower bounds on arithmetic circuits that compute a sum of powers of linear forms. In algorithm design and program verification, the extremal principle in the guise of 'take the minimal counterexample' is the standard engine behind infinite-descent correctness proofs for greedy and exchange algorithms.

Example: Enumerating all solutions of $x^2 - y^2 = 45$ by case analysis

Find all pairs of positive integers $(x, y)$ with $x > y$ satisfying $x^2 - y^2 = 45$ .

Solution

Factor the left side: $x^2 - y^2 = (x - y)(x + y) = 45$ . Since $x, y$ are positive integers with $x > y$ , both $d_1 = x - y$ and $d_2 = x + y$ are positive divisors of $45$ with $d_1 < d_2$ and $d_1 d_2 = 45$ ; they must also share the same parity (because $d_1 + d_2 = 2x$ is even), which is automatic here since $45$ is odd and hence every divisor of $45$ is odd.

The positive divisors of $45 = 3^2 \times 5$ are $1, 3, 5, 9, 15, 45$ , and pairing each divisor below $\sqrt{45}$ with the complementary one above it gives exactly $3$ exhaustive cases: $(d_1, d_2) \in \{(1, 45), (3, 15), (5, 9)\}$ . No other case is possible, since every divisor of $45$ appears in exactly one of these three pairs.

Solving $x = \dfrac{d_1 + d_2}{2}$ and $y = \dfrac{d_2 - d_1}{2}$ in each case: $(1, 45)$ gives $(x, y) = (23, 22)$ ; $(3, 15)$ gives $(x, y) = (9, 6)$ ; $(5, 9)$ gives $(x, y) = (7, 2)$ . Having checked every case exhaustively, these $3$ pairs are the complete solution set.

Example: Proving $\sqrt{2}$ is irrational via the extremal principle (infinite descent)

Prove that $\sqrt{2}$ is irrational, using the extremal (well-ordering) principle instead of the usual argument with lowest-terms fractions.

Solution

Suppose, for contradiction, that $\sqrt{2}$ is rational. Then the set $A = \{\, q \in \mathbb{Z}_{>0} : q\sqrt{2} \in \mathbb{Z}_{>0} \,\}$ is nonempty, so by the well-ordering principle it has a least element $q_0$ ; let $p_0 = q_0\sqrt{2} \in \mathbb{Z}_{>0}$ .

Since $1 < \sqrt{2} < 2$ , multiplying by $q_0$ gives $q_0 < p_0 < 2q_0$ . Define $q_1 = p_0 - q_0$ and $p_1 = 2q_0 - p_0$ ; both inequalities show $0 < q_1 < q_0$ and $0 < p_1 < q_0$ , so $q_1$ is a positive integer strictly smaller than $q_0$ .

Compute $q_1\sqrt{2} = (p_0 - q_0)\sqrt{2} = p_0\sqrt{2} - q_0\sqrt{2} = p_0\sqrt{2} - p_0$ . But $p_0 = q_0\sqrt{2}$ gives $p_0\sqrt{2} = q_0\sqrt{2}\cdot\sqrt{2} = 2q_0$ , so $q_1\sqrt{2} = 2q_0 - p_0 = p_1$ , a positive integer.

Thus $q_1 \in A$ and $q_1 < q_0$ , contradicting the minimality of $q_0$ as the least element of $A$ . The contradiction shows $A$ must in fact be empty, so $\sqrt{2}$ is irrational.

Research frontier as of 2026

As of 2026, the Sylvester–Gallai theorem still drives active research in algebraic complexity theory: 'robust' and higher-dimensional versions of the theorem (allowing points over $\mathbb{C}$ or finite fields, or allowing near-collinear rather than exactly collinear triples) are used to prove lower bounds for depth- $4$ arithmetic circuits and to construct locally correctable codes, following the line of work started by Barak, Dvir, Wigderson and Yehudayoff. On the tournament side, a 2025 survey by Schweser, Stiebitz and Toft revisits Rédei's original 1934 paper and shows it actually contains a stronger, largely overlooked theorem about mixed graphs (graphs with both directed and undirected edges) from which the odd-parity Hamiltonian-path count follows as a corollary, reopening interest in Rédei-type extremal arguments for mixed and hypergraph tournaments.

The Sylvester–Gallai theorem guarantees an ordinary line (through exactly $2$ points) for any finite set of $n \ge 3$ points in the plane, provided that:

A round-robin tournament (no ties) is played among $6$ teams. By Rédei's theorem, how many of the $6! = 720$ possible orderings of the teams are guaranteed to be a valid Hamiltonian path (a full ranking where each team beat the next)?

Using exhaustive case analysis on remainders modulo $3$ , how many integers from $1$ to $300$ are not divisible by $3$ ?

A proof 'by minimal counterexample' assumes the statement is false, takes the smallest failing instance, and derives an even smaller failing instance to reach a contradiction. Which property must the set of potential counterexamples have for this argument to be valid?

References

Martin Aigner, Günter M. Ziegler (2018). Proofs from THE BOOK · DOI:10.1007/978-3-662-57265-8
Thomas Schweser, Michael Stiebitz, Bjarne Toft (2025). The Tournament Theorem of Rédei revisited · arXiv:2510.10659 [preprint, not peer-reviewed]