Olympiad Combinatorics | Counting, Pigeonhole and Invariants

Olympiad Combinatorics: build a decision system for finite structure

Count objects by describing them uniquely

Counting is safest when every valid object has one description and every description produces one valid object. Before multiplying choices, ask whether choices are independent and whether two construction routes can create the same final object. This is why combinations, permutations, casework and complementary counting are not interchangeable formulas; each encodes a different description of the sample space.

Use the pigeonhole principle by designing the boxes

The elementary statement says that placing more objects than boxes forces some box to contain at least two objects. Olympiad difficulty lies in choosing the boxes. Residue classes, intervals, colours, last digits, subsets and distance categories can all become boxes. A strong solution explicitly identifies the objects, the boxes and the numerical imbalance that forces repetition.

Double counting proves identities by counting one set two ways

Instead of manipulating an identity algebraically, define a collection of objects and count it from two perspectives. Counting handshakes by people and by edges, or choosing a committee by whether a distinguished person is included, can turn a symbolic equality into a structural fact. This technique also prepares students for graph arguments and more advanced combinatorial identities.

Invariants compress long move sequences

If a problem allows repeated moves, simulating every sequence is usually impossible. Track something that every move preserves: parity, a colouring, a residue, a sum modulo n or another structural signature. If the starting and target states have different invariant values, the target cannot be reached. The proof must verify the invariant under every legal move.

Monovariants prove termination

A monovariant changes in one direction with every move. If it is bounded, the process cannot continue forever. This is useful in games, algorithms and rearrangement problems. The challenge is to choose a quantity that is simple enough to track but strong enough to constrain the process.

Extremal arguments choose the most constrained case

Pick a largest, smallest, earliest, latest or otherwise extreme object. Its extremality often removes possibilities that ordinary objects have. In a set of points, choose the closest pair; in a collection of integers, choose the smallest positive counterexample; in a graph, choose a vertex with minimum degree. The extremal object is a lens that makes global structure locally rigid.

Recursion turns a large configuration into smaller ones

Many counting problems can be partitioned according to the first move or final component. If a tiling begins with one type of tile, the remainder has one size; if it begins with another, the remainder has another size. This creates a recurrence. Students should derive the recurrence from a disjoint case split rather than guess it from numerical data.

Graph language can reveal hidden combinatorics

People and friendships, cities and roads, tasks and dependencies, or cells and allowed moves can be represented by vertices and edges. Degree counts, paths, cycles and connectivity then become available. Even without formal graph theory, drawing the right network can make a verbal problem much easier to reason about.

Common failures

Watch for multiplying dependent choices, double-counting symmetric arrangements, using pigeonhole without defining boxes, claiming an invariant without checking every move, and presenting numerical experimentation as proof. Error logs should record the structural mistake so the next practice problem targets the cause.

Transfer test

A student owns olympiad combinatorics when an unfamiliar problem triggers useful questions: What exactly am I counting? Can I count the complement? Is there forced repetition? What stays unchanged? What changes monotonically? Can I choose an extreme object? Can I represent the situation as a graph? The objective is strategic search, not a catalogue of named tricks.