Combinatorics & Games

Putting $n+1$ objects into $n$ boxes, there must be one box with $\ge2$. The difficulty always lies in designing the boxes:

• By remainders: among $n+1$ integers there must be two that are congruent $\bmod n$ (their difference is divisible by $n$).
• By odd part: taking $n+1$ out of $\{1,\dots,2n\}$, one must divide another (write $m=2^a\cdot(\text{odd})$, the odd part has only $n$ kinds).
• By odd/even lattice points $(\mathbb Z/2)^2$: among any 5 lattice points there must be two whose midpoint is a lattice point.
• Region splitting: a unit square divided into 4 small squares ⇒ among 5 points there must be two at distance $\le\tfrac{\sqrt2}{2}$.

After using the pigeonhole principle, don't forget a tightness construction to show the bound cannot be improved.

Choose an object that maximises or minimises a quantity, then prove it has the required property: otherwise a small adjustment would improve it, giving a contradiction.

For example, a maximum cut partitions a graph's vertices into two groups with as many crossing edges as possible. If a vertex had more neighbours in its own group than in the opposite group, moving it would increase the number of crossing edges, a contradiction. Thus each person has a number of friends in the opposite group $\ge$ the number in their own group. This also proves that a maximum cut of any graph contains $\ge$ half its edges.

Invariant: find a quantity that is conserved under each step of the operation (often some modulus), and use it to prove that 'the target state is unreachable' (numbers changed on a blackboard, coin flipping, parity of a puzzle).

Monovariant: find a quantity that is strictly monotone and bounded at each step, and prove that the process must terminate (e.g. regard the states of a row of coins as a binary number, which each operation strictly decreases).

Count the same quantity in two ways and set them equal. In graph theory, $\sum_v\deg(v)=2|E|$ (the handshaking lemma).

Application: Mantel's theorem — the number of edges in a triangle-free graph is $\le\lfloor n^2/4\rfloor$. Proof: triangle-free ⇒ the two endpoints of every edge are $\deg(u)+\deg(v)\le n$; summing over all edges gives $\sum\deg^2\le n|E|$, then by Cauchy–Schwarz $\sum\deg^2\ge\tfrac{(2|E|)^2}{n}$, and combining gives $|E|\le n^2/4$.

Divide-and-conquer induction: split the $2^{n+1}$ problem into $2^n$ subproblems — e.g. an $2^n\times2^n$ board with one square missing can be tiled by L-shaped trominoes (place one in the centre, creating a gap in each of the other three quadrants); $n$ lines divide the plane into $1+n+\binom n2$ regions (the $k$th line adds $k$ regions).

Insertion method: insert the new element into an already ordered sequence — every tournament has a Hamiltonian path (walk along the chain and insert at the point where the win/loss flips).

Stripping method: find a pair of adjacent targets, join them, strip them off, and induct — $2n$ points on a circle with $n$ red and $n$ blue can be joined by $n$ non-crossing red-blue chords.

Ramsey $R(3,3)=6$: among $6$ people there must be 3 who know each other or 3 who do not know each other (use pigeonhole on one person to force 3 edges of the same colour, then look inside these 3 people). $5$ people is not enough (pentagon + pentagram counterexample).

Erdős–Szekeres: $n^2+1$ distinct real numbers must contain a monotone subsequence of length $n+1$ (label each term with $(x_i,y_i)=$ (the longest increasing/decreasing length ending at $i$), pigeonhole + local extendability).

Happy Ending: 5 points in general position must contain a convex quadrilateral (classified by convex hull).