General

Small principles that do a lot of work.

Pigeonhole principle

If $n$ items go into $m$ boxes and $n>m$, some box holds at least two items.

Generalised: some box holds at least $\lceil n/m\rceil$ items.

Deceptively powerful. Typical uses:

Claim	Argument
Among any $n+1$ numbers from $[1,2n]$, one divides another	write each as $2^{a}q$ with $q$ odd; only $n$ odd values available
Some non-empty subset has sum divisible by $n$	the $n$ prefix sums mod $n$; two coincide (or one is 0)
Any sequence of $n^2+1$ distinct numbers has a monotone subsequence of length $n+1$	Erdős-Szekeres, via (increasing, decreasing) length pairs
Two of any 5 points in a unit square are within $\frac{\sqrt{2}}{2}$	quarter the square
A repeated state must occur within $k$ steps	the state space has size $k$
Birthday collisions	see Birthday Paradox

The prefix-sum-mod-$n$ argument is the one that appears most often in contests: it constructively finds the subarray, not just proves existence.

Extremal principle

Consider the largest / smallest / leftmost object satisfying the property.

The workhorse of constructive proofs. “Take the shortest counterexample” and derive a contradiction; “take the heaviest edge on the cycle” and show it is removable (MST cycle property); “take the vertex of minimum degree” and induct.

Invariants and monovariants

• Invariant — a quantity unchanged by every allowed move. If the start and target differ in it, the target is unreachable. (Parity, a sum mod $k$, a colouring, a permutation’s sign.)
• Monovariant — a quantity that only increases (or only decreases). Proves termination, and bounds the number of steps.

The classic: the 15-puzzle is solvable iff the permutation parity plus the blank’s row distance is even — a parity invariant.

Double counting

Count the same set two ways and equate. This proves:

${\sum }_v\mathrm{deg}(v)=2|E|\text{(handshake lemma)},\left(\genfrac{}{}{0ex}{}{n}{k}\right)=\left(\genfrac{}{}{0ex}{}{n}{n-k}\right),{\sum }_k\left(\genfrac{}{}{0ex}{}{n}{k}\right)=2^n.$

More generally, it is how most combinatorial identities are proved and how many counting problems are solved — count the contribution of each element rather than each configuration. The edge-contribution trick for tree distances is exactly this.

Symmetry

• If the problem is symmetric in some variables, the answer often is too — which lets you fix an ordering ($a\le b\le c$) and multiply by the number of arrangements.
• Symmetry breaking in search: fix that element 0 goes in the first group. Cuts a $k!$ factor.
• Burnside’s lemma counts objects up to symmetry — see Burnside and Pólya.

Useful sums and bounds

Sum	Closed form
${\sum }_{i=1}^{n}i$	$\frac{n(n+1)}{2}$
${\sum }_{i=1}^n{i}^2$	$\frac{n(n+1)(2n+1)}{6}$
${\sum }_{i=1}^n{i}^3$	${\left(\frac{n(n+1)}{2}\right)}^2$
${\sum }_{i=0}^n{r}^i$	$\frac{r^{n+1}-1}{r-1}$
$H_n={\sum }_{i=1}^n\frac{1}{i}$	$\approx \ln n+0.5772$
${\sum }_{i=1}^n\lfloor n/i\rfloor$	$\approx n\ln n$ — the divisor-sum bound
${\sum }_{p\le n}1/p$	$\approx \ln \ln n$
$n!$	$\approx \sqrt{2\pi n}(n/e{)}^n$ (Stirling)
$\left(\genfrac{}{}{0ex}{}{n}{k}\right)$	$\le {\left(\frac{en}{k}\right)}^k$
$\left(\genfrac{}{}{0ex}{}{2n}{n}\right)$	$\approx \frac{4^n}{\sqrt{\pi n}}$

The harmonic bound $\sum \lfloor n/i\rfloor \approx n\ln n$ is why “for each $i$, loop over multiples of $i$” is $O(n\log n)$ — see Sieve Techniques.

Modular arithmetic reminders

Full treatment in Modular Arithmetic; the traps in one line each:

• $(a-b)\mathrm{mod}m$ can be negative in C++ — write ((a - b) % m + m) % m.
• Division needs a modular inverse, which exists only when $\gcd (b,m)=1$.
• $a^k\mathrm{mod}m$ reduces the exponent modulo $\phi (m)$, not $m$.
• long long overflows at $9.2\cdot 10^{18}$; two values near $10^{18}$ multiplied need __int128.

See also: Combinatorics · Proof Techniques · Constructive Algorithms