iv. Proof Techniques

Proof is what turns “passes the samples” into “is correct”. You don’t need full rigour in a contest, but you need the key lemma. The patterns below cover most of it.

General tools

Tool	Shape	Typical use
direct / loop invariant	state a property; show it holds initially, is preserved, and implies the answer at termination	binary search, two pointers, sweeps
pigeonhole (simple)	$n + 1$ items into $n$ boxes forces one box with $\geq 2$	hashing collisions, cycle existence, 100 prisoners cycle bound
pigeonhole (generalized)	$n$ items into $k$ boxes forces one box with $\geq ⌈ n / k ⌉$	at least one of $k$ cases must handle $\geq n / k$ load
pigeonhole (averaging)	if the average of $n$ values is $\geq v$ , at least one value is $\geq v$ (and at least one is $\leq v$ )	existence of a “good enough” element without constructing it
induction	base case plus “smaller cases imply this one”, on size, depth, value, or number of operations	DP, tree algorithms, recursive constructions
strong induction / minimal counterexample	assume all smaller cases, or take the smallest failure and build a smaller one	graph theory, number theory
contradiction	assume the property fails and derive an impossibility from optimality or an invariant	greedy optimality
construction	an explicit procedure plus proof that each step is legal, it terminates, and the output is valid	existence claims
bound + construction	prove $OPT \geq B$ , then build a solution of value $B$	“minimum number of operations”
double counting	count one set two ways	identities, degree arguments
bijection	build a one-to-one map between two sets	Catalan families, partition identities
probabilistic method	if a random object has the property with positive probability, one exists	existence of good colourings, hashing bounds

A loop invariant must be true mid-loop, not only at the end. For lower_bound on $[l, r)$ : everything below $l$ is $< x$ and everything at or after $r$ is $\geq x$ . Each step preserves this, and $l = r$ gives the answer.

Greedy

Exchange argument. Take any optimal solution $O$ . At the first place it differs from greedy, swap in the greedy choice and show the result is still feasible and no worse. By induction some optimal solution agrees with greedy everywhere.

Adjacent exchange for ordering problems. For a cost of a sequence, compare $\dots a b \dots$ with $\dots b a \dots$ . If the difference depends only on $a$ and $b$ , greedy sorts by the key that makes ” $a$ first” better. You must check the induced relation is a strict weak order (transitive). Example: minimise $\sum w_{i} C_{i}$ by sorting on $p_{i} / w_{i}$ (Smith’s rule).

Greedy stays ahead. Show that after $k$ steps greedy’s progress measure is at least as good as any solution’s after $k$ steps. Interval scheduling: the $k$ -th greedy interval ends no later than the $k$ -th interval of any feasible schedule.

Matroids. If the feasible sets form a matroid (hereditary plus the exchange property), the weight-sorted greedy is optimal for every weight function. That covers MST (graphic matroid), linearly independent sets (linear matroid), and scheduling unit jobs with deadlines (transversal/scheduling matroid). Bipartite matching is not a matroid; it’s an intersection of two partition matroids (Matroids).

Cut and cycle properties. For MST: the lightest edge crossing a cut is in some MST, and the strictly heaviest edge of a cycle is in none. Kruskal, Prim and Borůvka are all instances.

Counterexamples are part of the craft: before trusting a greedy, try to break it with 3-4 elements by brute force.

DP

Say exactly what $d p [s]$ means, in words.
Optimal substructure: if the part of an optimal solution inside subproblem $s$ weren’t optimal, replacing it would improve the whole. This replacement argument also tells you what the state must remember: everything the replacement could affect.
Completeness: the transition enumerates every possible last (or first) decision, so the optimum is among the candidates. Soundness: every candidate is a feasible solution.
Induct along a topological order of states. Check base cases and that unreachable states can’t leak in.

Where the replacement argument fails, the state is missing information. Longest simple path on a general graph depends on the set of visited vertices; on a DAG it doesn’t, so the vertex-only DP works.

DP optimisation proofs: monotonicity of the optimal split point ( $o pt (i) \leq o pt (i + 1)$ ) follows from the quadrangle inequality $w (a, c) + w (b, d) \leq w (a, d) + w (b, c)$ for $a \leq b \leq c \leq d$ . Convexity of $f (k)$ in the number of groups justifies the Aliens trick. Both are covered in the DP chapter.

Graph algorithms

Algorithm	Key lemma
BFS	vertices leave the queue in non-decreasing distance; induct on distance
Dijkstra	when $u$ is popped, $d [u]$ is final: any shorter path leaves the settled set through an edge to some $x$ with $d [x] \leq d [u]$ , and non-negative weights make the rest of the path non-negative
Bellman-Ford	after $k$ rounds, $d [v] \leq$ shortest walk with $\leq k$ edges; a relaxation in round $n$ proves a negative cycle
Floyd-Warshall	after phase $k$ , $d [i] [j]$ is shortest using intermediates in ${1.. k}$
DFS, white-path theorem	$v$ becomes a descendant of $u$ iff at time $u$ is discovered there’s a path of unvisited vertices from $u$ to $v$ ; this gives edge classification and SCC proofs
Tarjan SCC / bridges	low-link: $l o w [v]$ is the smallest discovery time reachable via tree edges then one back edge; $v$ is an SCC root iff $l o w [v] = t in [v]$
Topological sort	a DAG has a source; removing it leaves a DAG; equivalently, reverse DFS finishing order
Max-flow = min-cut	if the residual graph has no $s$ - $t$ path, the vertices reachable from $s$ define a cut whose capacity equals the flow
Kuhn / Berge	a matching is maximum iff there’s no augmenting path
König	in bipartite graphs, max matching = min vertex cover (from the residual reachability of the max flow)
Hall	a perfect matching of the left side exists iff $∣ N (S)∣ \geq ∣ S ∣$ for every $S$
2-SAT	satisfiable iff no $x$ and $\neg x$ share an SCC; assign $x$ true iff its SCC comes later in topological order

Data structures

Invariant first: heap order, BST order, “each segment tree node stores the aggregate of its range with all its ancestors’ tags applied”, “the deque is increasing”.
Complexity: potential functions. Splay: $Φ = \sum lo g (size)$ gives the access lemma. Segment tree beats: $Φ$ = number of distinct values in nodes, or the number of “tags”. Union by size: an element’s set doubles each time its root changes.
Randomised structures: treap depth is $O (lo g n)$ in expectation, by the same analysis as random BST insertion and quicksort: $x_{i}$ is an ancestor of $x_{j}$ iff it has the smallest priority among $x_{i} .. x_{j}$ , with probability $1/ (∣ i - j ∣ + 1)$ , and summing gives $2 H_{n}$ .

Number theory and algebra

Bézout: $g cd (a, b)$ is the smallest positive integer combination $a x + b y$ . Inverses exist iff $g cd = 1$ .
Fermat/Euler: $a^{φ (m)} \equiv 1$ for $g cd (a, m) = 1$ , because multiplying by $a$ permutes the units.
Lagrange: in a group, the order of an element divides the group order. This is behind primitive root tests and order-finding.
A polynomial of degree $d$ over a field has at most $d$ roots. That gives Schwartz-Zippel (a random evaluation catches a nonzero polynomial with probability $\geq 1 - d /∣ S ∣$ ), the uniqueness of interpolation, and why $x^{2} \equiv 1 (mod p)$ only has roots $\pm 1$ (Miller-Rabin).
Deterministic Miller-Rabin for 64-bit inputs with the bases ${2, 325, 9375, 28178, 450775, 9780504, 1795265022}$ is a verified computational fact, not dependent on GRH.
Lucas: $(1 + x)^{p} \equiv 1 + x^{p} (mod p)$ , so $(1 + x)^{n}$ factors along base- $p$ digits.

Counting

Bijection: Dyck paths, binary trees, triangulations and non-crossing matchings are all Catalan via explicit maps. The reflection principle counts paths that cross a line: reflect the prefix up to the first touch.
Double counting: $\sum_{k} k (k n) = n 2^{n - 1}$ counts (set, marked element) pairs.
Burnside: the number of orbits is the average number of fixed points, by counting pairs $(g, x)$ with $g x = x$ two ways.
Generating functions: sums of independent choices multiply; that’s a proof as well as an algorithm.
Sign-reversing involutions: to show an alternating sum is small, pair objects of opposite sign and count the unpaired fixed points (inclusion-exclusion, LGV lemma).

Games

Induct on the game tree: a position is losing iff every move goes to a winning position. Minimax is the same induction one level up: the minimax value at depth $d$ is optimal under optimal play given that the value at depth $d + 1$ already is, bottoming out at terminal positions.
Alpha-beta pruning doesn’t change the answer: a branch is pruned only once its value is proven to lie outside the window $[α, β]$ that the rest of the tree could possibly use, so the pruned subtree’s exact value can never affect the final minimax value returned at the root.
Sprague-Grundy: a sum of games has Grundy value equal to the XOR of components. Proof: from XOR $0$ every move makes it nonzero; from nonzero there’s a move to $0$ (by the definition of mex).
Strategy stealing: if the first player loses, the first player can “pass” by making a move that does no harm, then steal the second player’s strategy. That’s a contradiction, so the first player wins (Hex, Chomp). It’s non-constructive.
Pairing / mirror strategy: pair up moves so every move has a reply that restores a symmetric or paired position.

Geometry

Convex hull (Graham scan / Andrew’s monotone chain): maintain the invariant that the last three points on the stack form a left turn; on a right turn, pop before pushing. Proof by orientation test at every step means the output can never contain a right turn, i.e. it is convex, and the pops never discard a true hull vertex (a popped point is strictly inside the triangle formed around it).
Rotating calipers: the antipodal-pair angle is monotone as the calipers rotate a full turn, so each edge direction is visited once and the total work across all antipodal pairs is $O (n)$ , not $O (n^{2})$ .
Sweep line: process events in sorted sweep-coordinate order and maintain the invariant that the active set is exactly the structures currently intersecting the sweep line; correctness reduces to showing every structural change (an insertion, deletion, or intersection) is itself an event, so nothing is missed between events.

Lower bounds

Decision trees: any comparison sort has $n!$ leaves, so depth $\geq lo g_{2} n! = Ω (n lo g n)$ . With $k$ -ary answers, $lo g_{k} (# outcomes)$ queries.
Adversary: answer queries to keep as many inputs consistent as possible. Finding the max needs $n - 1$ comparisons (every non-max must lose once); max and min together need $⌈ 3 n /2 ⌉ - 2$ .
Reductions (fine-grained): if solving $A$ fast would solve $B$ fast, and $B$ is believed hard (3SUM, APSP, OV), then so is $A$ . Recognising a 3SUM-hard or NP-hard problem tells you a constraint must be small.
Reductions (NP-hardness): rarer in CP, but recognise the shape: a polynomial-time reduction from a known NP-hard $B$ to $A$ that preserves yes/no answers proves $A$ is NP-hard too. For optimization problems, a gap reduction (distinguishing instances with value $\geq v$ from value $< (1 - ϵ) v$ ) proves hardness of approximation, not just of exactness.

Backtracking and branch and bound

Correctness needs two things: the search is exhaustive (every candidate is visited if no branch is pruned, usually by induction on the decision prefix), and every prune is safe (the bounding function is a genuine upper/lower bound on anything reachable from that branch, so discarding it can never discard the optimum). A weak bound is still correct, just slow — bound quality is a performance property, not a correctness one.

Randomised algorithms

Las Vegas: always correct, random running time. Bound the expectation with linearity of expectation (quicksort, treaps, randomised incremental geometry via backward analysis).
Monte Carlo: may be wrong with small probability. Repeat to amplify, and bound the error with a union bound or Chernoff: the sum of independent indicators deviates from its mean $μ$ by a factor $(1 \pm δ)$ with probability $\leq 2 e^{- δ^{2} μ /3}$ .
Hash collisions: with $q$ comparisons and a modulus $M$ , the failure probability is about $q \cdot (degree) / M$ . Polynomial hashes of length $n$ collide with probability $\leq n / M$ per pair.

Habits

Write a three-sentence proof sketch before coding: the invariant, the exchange, or the recurrence’s meaning.
Prove the edge cases: $n = 1$ , ties, empty sets, all equal.
Keep a list of greedy counterexamples (non-canonical coin systems, earliest-start interval scheduling, densest-first knapsack). They train scepticism.
When an editorial says “it’s easy to see”, find the lemma it skipped — that’s exactly the “why this works” paragraph to focus on, not the implementation details around it.
Explain the proof out loud, or to a teammate. Teaching exposes the gaps a silent read-through hides.

Proof discovery

Finding why an idea works, before or instead of a formal proof.

Step	How
guess with data	brute force small cases, look at the optimal objects, not only the values
strengthen the claim	a stronger statement is often easier to prove by induction (it gives a stronger hypothesis)
look at an optimal solution	assume an optimum that differs from your greedy at the first position; can you swap it towards yours without loss? (exchange argument)
find what never changes	invariants explain impossibility and reachability
find what always improves	potentials explain termination and amortized costs
attack your own claim	generate random and adversarial cases to break it; a counterexample is progress
prove the lower bound separately	”at least $k$ ” (counting, adversary, invariant) plus “at most $k$ ” (construction)

Idea type	Proof pattern
greedy	exchange argument, staying ahead, matroid structure
DP	states capture everything relevant (optimal substructure); order is topological
DP optimization	quadrangle inequality / monotone argmin; convexity for Aliens and slope trick
construction	verify by a checker for all small parameters; necessary conditions match
data structure	invariant per node; amortized potential

Examples of each pattern are listed in 🐬 Proof Techniques.

whoashish's cp notes

Directory