ii. Invariants, Parity and Extremal Arguments

The three arguments behind most ad hoc and constructive problems:

• An invariant proves something is impossible.
• A monovariant proves a process terminates and bounds the number of moves.
• An extremal object gives the first step of a proof or construction.

Invariants

An invariant is a quantity that no allowed move changes. If start and target differ in it, the target is unreachable.

Move	Preserved
swap two elements	permutation parity flips, so it’s preserved under pairs of swaps
replace $a,b$ by $a+b$	total sum, gcd of all
replace $a,b$ by $|a-b|$	gcd of all, parity of the sum
add $k$ to two elements	pairwise differences mod $k$
flip a cell and its neighbours	XOR of the cells in a fixed “test set” orthogonal to every move (linear algebra over ${\mathbb{F}}_2$)
reverse a subarray of length $L$	multiset; parity of the permutation changes by $\lfloor L/2\rfloor$
adjacent swap of different values	inversion count changes by exactly $\pm 1$
slide a tile in the 15-puzzle	permutation parity + row of the blank, mod 2
rotate a cube face	corner orientation sum mod 3, edge orientation mod 2, permutation parities equal

Candidates to try in order: sum, sum mod $k$ (try $k=2$ first, then 3), XOR, gcd, the multiset or sorted order, inversions, a colouring count, a weighted sum $\sum w_i{a}_i$ with weights chosen so every move preserves it.

Linear invariants over ${\mathbb{F}}_2$. When every move adds (XORs) a fixed vector to the state (lights out, toggling a row/column, flipping a path), the reachable set is the start plus the span of the move vectors. Reachability is a linear system, and the invariants are the vectors orthogonal to all moves. Solve with Gaussian elimination or an XOR basis.

Necessary and sufficient. An invariant only proves impossibility. The standard solution shape is:

1. compute the invariant and output “impossible” if it differs;
2. otherwise construct a solution, usually by induction (fix one element, recurse on the rest).

Often the answer is that the invariant is the only obstruction. Brute-force tiny cases to check that before proving it — this step is not optional: a brute force over $n\le 6$ answers “which cases are possible” in seconds and makes the invariant visible, instead of guessing at a pattern from nothing.

Monovariants and termination

A monovariant only increases or only decreases. A non-negative integer that strictly decreases at each step proves termination, and its initial value bounds the number of steps.

Process	Monovariant
bubble sort / adjacent swaps	inversions: exactly $\mathrm{inv}$ swaps are necessary and sufficient
Euclid’s algorithm	$\min (a,b)$; at least halves every two steps
local improvement of a cut or a matching	objective value (bounded integer)
augmenting paths	flow value
”if two neighbours are out of order, fix them”	$\sum$ of squares, or the lexicographic order of the sorted state
chip-firing	a potential such as ${\sum }_v{\text{chips}}_v\cdot \text{dist}(v)$
Stable matching (Gale-Shapley)	each proposer moves down their list

A real number decreasing toward 0 need not terminate; you need a well-founded measure (bounded integers, or lexicographic tuples of them).

Bounding the answer: “minimum number of operations” problems are often: show each operation decreases potential $\Phi$ by at most $c$, so the answer is at least $\lceil {\Phi }_0/c\rceil$, then construct a sequence achieving it.

Parity and colouring

Fact	Use
$\sum \mathrm{deg}=2m$, so the number of odd-degree vertices is even (in any subgraph too)	Euler paths, Chinese postman, Christofides, $T$-joins; Sperner’s lemma and “handshake on a hypergraph” generalise this and give a combinatorial proof of Brouwer’s fixed-point theorem
bipartite $⟺$ no odd cycle	2-colour by BFS
a permutation with $c$ cycles on $n$ elements has sign $(-1{)}^{n-c}$	sorting by swaps needs $n-c$ swaps
$\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ odd $⟺$ $k\subseteq n$ bitwise	Lucas mod 2, Sierpinski patterns
$a+b\equiv a-b\equiv a\oplus b(\mathrm{mod}2)$	parity of sums
a closed walk in a bipartite graph has even length	grid walks: $(x+y)\mathrm{mod}2$ flips every step
knight moves change square colour	closed knight tours need an even number of squares

Colouring arguments. Colour the board so every piece covers a fixed count of each colour:

• Chessboard with opposite corners removed has two more of one colour, so no domino tiling.
• $1\times k$ bars on an $m\times n$ board: colour cell $(i,j)$ with $(i+j)\mathrm{mod}k$. Each bar covers one of each colour, so every colour count must be equal.
• $(i\mathrm{mod}2,j\mathrm{mod}2)$ four-colouring for $2\times 2$-ish pieces and L-trominoes.
• Conway’s soldiers: weight a cell at Manhattan distance $d$ from the target by ${\omega }^d$ with $\omega =(\sqrt{5}-1)/2$ (so ${\omega }^2+\omega =1$). Every jump keeps the total weight from increasing, and the infinite half-plane has total weight exactly 1 relative to row 5, so row 5 is unreachable.

The rule: when stuck on “is it possible”, tabulate small cases and look at them mod 2, then mod 3, then under a colouring, then as a weighted sum.

Try mod 2 first, always

It is the cheapest hypothesis and correct more often than any other single guess. If mod 2 fails, try mod 3, then a colouring, then a weighted sum. A potential function (strictly monotone rather than invariant) is the fallback once no fixed quantity works — that’s a monovariant, not an invariant.

More parity facts, and where they decide an answer outright rather than just narrowing the search:

Fact
${\sum }_{i=1}^{n}i=\frac{n(n+1)}{2}$, parity has period 4 in $n$	odd for $n\equiv 1,2(\mathrm{mod}4)$, even for $n\equiv 0,3(\mathrm{mod}4)$
Eulerian circuit iff every degree even; Eulerian path iff exactly two odd	Euler Tours
Chinese postman: pair up the (even number of) odd-degree vertices by shortest paths and duplicate those paths	makes every degree even, so an Eulerian circuit exists on the duplicated multigraph
misère Nim’s deviation from normal Nim depends on the parity of the number of heaps of size 1	Nim
”take 1 or 2 stones” has Grundy value $n\mathrm{mod}3$	parity generalised to mod 3
$L$-trominoes tile a $2^n\times 2^n$ board with any one cell removed	classic induction: quarter the board, the removed cell’s quadrant needs one more tromino at the centre, which also covers one cell in each of the other three quadrants, recursing
triangular or toroidal boards	the same colouring idea re-indexes: 3-colour a triangular grid by $(i-j)\mathrm{mod}3$; a toroidal colouring just wraps the indices mod the board’s period

The extremal principle

Consider the largest, smallest, first, last, or otherwise extreme object. It has properties nothing else has.

Minimal counterexample: assume the claim fails, take the smallest counterexample, and build a smaller one. This is strong induction in disguise.

Extremal element of an optimal solution: take an optimal solution and look at its extreme part (heaviest edge, last job, leftmost point). Show it can be exchanged or removed without loss. That’s the core of exchange arguments.

Claim	Extremal object
every tree with $n\ge 2$ vertices has $\ge 2$ leaves	endpoints of a longest path
min degree $\ge 2$ implies a cycle	longest path: its endpoint’s other neighbour lies on the path
min degree $\ge k$ implies a path of length $k$ and a cycle of length $\ge k+1$	longest path again
every DAG has a source	start of a longest path
every tournament has a Hamiltonian path	insert vertices one by one, or take a longest path
every tournament has a king (reaches all in $\le 2$ steps)	vertex of maximum out-degree
the heaviest edge of a cycle isn’t in some MST	cycle property via exchange
Sylvester-Gallai	smallest positive distance from a point to a line through two others
$\sqrt{2}$ irrational	minimal denominator

Where to look:

Setting	Extreme
graphs	longest path, max/min degree, heaviest edge, largest component, deepest DFS vertex
trees	leaves, centroid, diameter endpoints, deepest node
sequences	maximum (split the array at it), first violation, longest run
geometry	leftmost/lowest point (on the hull), closest pair, extreme point in a direction
constructions	most constrained element first; the largest value placed first

Proof: every tree with $n\ge 2$ vertices has $\ge 2$ leaves

Take the longest path in the tree, $v_0,\dots ,v_k$ ($k\ge 1$ since $n\ge 2$). Its endpoint $v_0$ has degree 1: any neighbour other than $v_1$ would either extend the path (if not already on it) or close a cycle (if it were some $v_i$, $i\ge 2$, contradicting that trees are acyclic) — both impossible for a longest path. The same argument applies to $v_k$, and $v_0\ne v_k$ since $k\ge 1$, giving two distinct leaves. $■$

Proof: min degree $\ge 2$ implies a cycle

Take the longest path $v_0,\dots ,v_k$. Since $\mathrm{deg}(v_k)\ge 2$, it has a neighbour other than $v_{k-1}$; that neighbour cannot be a new vertex (it would extend the path, contradicting maximality), so it must be some $v_i$ on the path with $i<k-1$ — giving the cycle $v_i,v_{i+1},\dots ,v_k,v_i$. $■$

Proof: every DAG has a source

Take the longest directed path $v_0\to \cdots \to v_k$ (exists and is finite since the graph is acyclic and finite). If $v_0$ had an incoming edge from some $u$: if $u$ is not on the path, prepending it extends the path, contradicting maximality; if $u=v_i$ for some $i$ on the path, the edge $u\to v_0$ together with the path segment $v_0\to \cdots \to v_i$ closes a cycle $v_i\to v_0\to \cdots \to v_i$, contradicting acyclicity. So $v_0$ has in-degree 0. $■$

Proof: the heaviest edge of a cycle isn't in some MST

Suppose it were. Removing it from the MST splits the tree into two components; the cycle (minus that edge) is a path between the same two endpoints, so it must cross the cut again at some other edge — which, since the removed edge was strictly heaviest on the cycle, is strictly lighter. Swapping the heavy edge for that lighter crossing edge keeps the result a spanning tree (still connected, still $n-1$ edges, no cycle reintroduced) with strictly smaller total weight, contradicting that the original was an MST. $■$

Proof: Sylvester-Gallai

Among all (point, line-through-two-other-points) pairs with the point not on the line, take the one minimising the perpendicular distance from the point to the line (finitely many pairs, so a minimum exists, and at least one pair exists since the points are not all collinear). Call the point $P$, foot of the perpendicular $F$, and the line $\ell$ through at least three of the points, $A,B,C$ (assume for contradiction $\ell$ has 3 or more). Among $A,B,C$, two lie on the same side of $F$ along $\ell$ (pigeonhole: 3 points split by $F$ into left/right); say $A$ is strictly between $F$ and $B$. The perpendicular distance from $A$ to the line $PB$ is then strictly less than $PF$: $A$ lies strictly inside the right triangle $PFB$ (on segment $FB$, with $P$ off the line), and the distance from any point on a leg of a right triangle to the hypotenuse is less than the triangle’s height from the right-angle vertex — here that height is exactly $PF$. So $(A,PB)$ is a pair with strictly smaller distance than $(P,\ell )$, contradicting minimality. The minimising line therefore has exactly 2 points. $■$

Proof: $\sqrt{2}$ is irrational (via the extremal principle)

Suppose $\sqrt{2}=p/q$ with positive integers $p,q$ and $q$ minimal among all such representations (exists by well-ordering). Then $p^2=2q^2$. Since $1<2<4$, taking square roots gives $1<p/q<2$, i.e. $q<p<2q$. Set $p^{\prime }=2q-p$ and $q^{\prime }=p-q$; both are positive integers ($p<2q\Rightarrow p^{\prime }>0$; $p>q\Rightarrow q^{\prime }>0$) with $q^{\prime }=p-q<q$ (a smaller denominator). Direct algebra, using only $p^2=2q^2$: $p^{\prime 2}-2q^{\prime 2}=(2q-p{)}^2-2(p-q{)}^2=(4q^2-4pq+p^2)-2(p^2-2pq+q^2)=2q^2-p^2=0$, so $p^{\prime 2}=2q^{\prime 2}$, i.e. $p^{\prime }/q^{\prime }=\sqrt{2}$ too — a representation with a strictly smaller denominator, contradicting minimality of $q$. $■$ (This avoids the usual parity/infinite-descent argument entirely, using “minimal counterexample” instead.)

Splitting at the maximum is a great general tool: many problems on arrays decompose recursively around the position of the maximum (Cartesian tree, “divide at the max” with small-to-large to get $O(n\log n)$).

A linear function on an interval is extremised at an endpoint, and a convex function on a polytope at a vertex. Only test the boundary values.

Pigeonhole

$n>rm$ items in $m$ boxes force some box to hold at least $r+1$.

Application
some non-empty subarray has sum divisible by $n$	$n+1$ prefix sums mod $n$; find two equal in $O(n)$
among $n+1$ numbers in $[1,2n]$ two are coprime, and one divides another	consecutive pairs; odd parts
iterating $x\to f(x)$ on a set of size $m$ repeats within $m+1$ steps	cycle detection, period finding
a string of length $>|\Sigma |$ repeats a letter	answer bounded by alphabet size
bounded answer means brute force	”if $n>K$ the answer is always yes”, so only search when $n\le K$
Erdős-Szekeres: $(r-1)(s-1)+1$ distinct numbers contain an increasing run of length $r$ or a decreasing one of length $s$	LIS/LDS bounds; $\lceil \sqrt{n}\rceil$
distinct prefix gcds/ORs/ANDs ending at a position	at most $\log V$
birthday bound: $\sqrt{2N\ln (1/(1-p))}$ random samples from $N$ collide with probability $p$	hashing collision estimates

Pigeonhole proves existence. You still have to scan for the pair.

Dilworth and Mirsky. In a partial order, the size of the largest antichain equals the minimum number of chains covering it (Dilworth), and the length of the longest chain equals the minimum number of antichains (Mirsky). For sequences: the minimum number of non-increasing subsequences covering $a$ equals the length of the longest strictly increasing subsequence. Computing a minimum chain cover in a general DAG is a bipartite matching (path cover).

Proof: Mirsky's theorem (the easy direction of the pair)

Longest chain $\ge$ minimum antichain cover is immediate: a chain of length $k$ has one element in each of at least $k$ different antichains of any cover (no two elements of a chain can share an antichain, since a chain’s elements are pairwise comparable and an antichain’s are not), so any cover needs $\ge k$ antichains, in particular $\ge$ the longest chain’s length.
Equality (a cover achieving exactly the longest chain length $k$ exists): let $\ell (x)$ be the length of the longest chain ending at $x$. Each level set $\{x:\ell (x)=i\}$ is an antichain (if $x<y$ with $\ell (x)=\ell (y)=i$, then extending the chain ending at $x$ by $y$ gives $\ell (y)\ge \ell (x)+1$, contradiction), and there are exactly $k={\max }_x\ell (x)$ non-empty level sets, covering every element. $■$
(Dilworth’s theorem, the antichain/chain-cover dual, is substantially harder — the standard proof is by induction using König’s theorem or a direct exchange argument; it is the one genuinely deep result of the pair.)

Proof: Erdős-Szekeres

Among $(r-1)(s-1)+1$ distinct numbers, assign to each element $x$ the pair $(a_x,b_x)$ where $a_x$ is the length of the longest increasing run ending at $x$ and $b_x$ the length of the longest decreasing run ending at $x$. If $x<y$ (in position) and the value at $x$ is less than at $y$, $a_y\ge a_x+1$ (extend the increasing run); if the value at $x$ exceeds the value at $y$, $b_y\ge b_x+1$. So for $x\ne y$, $(a_x,b_x)\ne (a_y,b_y)$ (the elements are distinct values, so one of the two cases applies, incrementing one coordinate). If no increasing run has length $\ge r$ and no decreasing run has length $\ge s$, then $a_x\in \{1,\dots ,r-1\}$ and $b_x\in \{1,\dots ,s-1\}$ for every $x$, giving only $(r-1)(s-1)$ possible distinct pairs — but there are $(r-1)(s-1)+1$ elements, each with a distinct pair, a contradiction (pigeonhole). $■$