Olympiad Combinatorics

To prove a process can never reach a state, find a quantity it preserves (parity, a sum mod $m$, a coloring count) that differs between start and goal. To prove it terminates, find a monovariant — an integer quantity that strictly decreases. The 1..2026 difference game: the parity of the sum is invariant and odd, so the last number is odd — at least $1$.

Look at the largest, smallest, or closest object — extremeness forces structure. Pigeonhole with $kn + 1$ objects in $n$ boxes forces $k + 1$ together; the generalized and infinite versions and "pigeonhole on residues" cover a huge fraction of olympiad existence proofs.

Count incidences two ways to derive an identity or inequality (the handshake lemma is the prototype). Graph theory: degree sums, trees have $n - 1$ edges, bipartite iff no odd cycle, Mantel/Turán bound edges without a triangle ($\le n^2/4$; $25$ for $n = 10$). Model the problem as a graph the moment "pairs" or "relations" appear.