Combinatorics, Pigeonhole, Invariants and Induction — IOQM, RMO and INMO

Weightage: Combinatorics is the most unpredictable of the four olympiad areas, since problems rarely repeat, but a small set of ideas recurs: counting two ways, pigeonhole, invariants, induction and extremal choice. The IOQM leans towards counting, and the RMO and INMO towards proof.

1. Counting that is exact

The basic tools are the rule of sum and rule of product, permutations $n!$, combinations $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ and arrangements with repeated items $\frac{n!}{n_1!n_2!\cdots }$.

Stars and bars. The number of non-negative integer solutions of $x_1+\cdots +x_k=n$ is $\left(\genfrac{}{}{0ex}{}{n+k-1}{k-1}\right)$. With each $x_i\ge 1$ it is $\left(\genfrac{}{}{0ex}{}{n-1}{k-1}\right)$.

Worked example. Distribute 10 identical sweets among 4 children, each getting at least one. The count is $\left(\genfrac{}{}{0ex}{}{9}{3}\right)=84$.

Inclusion-exclusion counts a union:

$|A_1\cup \cdots \cup A_n|=\sum |A_i|-\sum |A_i\cap A_j|+\sum |A_i\cap A_j\cap A_k|-\cdots$

Worked example. The number of integers from 1 to 100 divisible by 2, 3 or 5 is $50+33+20-16-10-6+3=74$.

Derangements (permutations with no fixed point) number $D_n=n!{\sum }_{k=0}^n\frac{(-1{)}^k}{k!}$, so $D_4=9$.

2. Bijections and double counting

To count a set, set up a bijection with a set that is easier to count. To prove an identity, count the same set in two ways.

Worked example. Prove ${\sum }_{k=0}^n\left(\genfrac{}{}{0ex}{}{n}{k}\right)=2^n$. Count the subsets of an $n$-element set by size ($k$ elements: $\left(\genfrac{}{}{0ex}{}{n}{k}\right)$ ways) and also as $2^n$, a yes or no choice for each element.

A handshake-style argument is double counting: the sum of degrees in a graph equals twice the number of edges, so the number of odd-degree vertices is even.

3. The pigeonhole principle

If $n+1$ objects go into $n$ boxes, some box holds at least two. More generally, with $m$ objects in $n$ boxes, some box holds at least $\lceil m/n\rceil$.

The skill is choosing the boxes.

Worked example. Among any 5 points in a unit square, two are within $\frac{\sqrt{2}}{2}$ of each other. Divide the square into four quarter squares of side $\frac{1}{2}$, whose diagonal is $\frac{\sqrt{2}}{2}$. Five points lie in four squares, so two share a square.

Worked example. From the numbers $1,\dots ,2n$ pick $n+1$. Two are consecutive. Use the $n$ boxes $\{1,2\},\{3,4\},\dots ,\{2n-1,2n\}$.

4. Invariants and monovariants

An invariant is a quantity that does not change under the allowed moves. If the start and target differ in the invariant, the target is unreachable. Typical invariants are parity, a sum modulo $m$ and a colouring count.

Worked example. A $8\times 8$ board has two opposite corners removed. It cannot be tiled by $1\times 2$ dominoes. Colour it like a chessboard: the removed corners have the same colour, so the board has 30 squares of one colour and 32 of the other, but each domino covers one of each.

A monovariant changes in only one direction and must stop, which proves a process terminates.

5. Induction and extremal arguments

Induction proves a statement for every $n$ from a base case and a step $P(n)\Rightarrow P(n+1)$. Strong induction may assume all earlier cases. Look for the step where you remove one object or add one element.

The extremal principle: consider the largest, smallest, longest or closest object, and show it has a special property. A finite nonempty set of integers has a minimum, and that fact alone proves many results.

Worked example. Among $n$ people, show there are two with the same number of acquaintances (for $n\ge 2$). Degrees run from $0$ to $n-1$, but a person of degree $0$ and a person of degree $n-1$ cannot both exist. So the degrees take at most $n-1$ values among $n$ people, and pigeonhole finishes it.

6. Graph theory basics

A graph has vertices and edges. A tree on $n$ vertices is connected with $n-1$ edges and no cycles. A graph is bipartite exactly when it has no odd cycle. An Euler circuit exists in a connected graph if and only if every vertex has even degree.

Worked example. In a tournament (every pair plays once, no draws), the sum of wins over all players is $\left(\genfrac{}{}{0ex}{}{n}{2}\right)$, the number of games.

7. Games and strategies

For a take-turns game, determine the winning positions by working backwards from the end. A symmetry strategy lets the second player copy the first in a mirror image. A strategy-stealing argument shows that in some games the first player cannot lose.

8. Counting in the IOQM

Integer answers mean exact counts. Break the count into cases that are disjoint and exhaustive, check with a small case, and look for a complementary count if the direct count is awkward.

Common traps

• Counting the same arrangement twice because objects are identical.
• Pigeonhole with poorly chosen boxes.
• An invariant that does not separate the start from the target.
• Induction that proves the step only for $n$ large, leaving small cases untested.
• Forgetting the empty or trivial case in inclusion-exclusion.

Memory aids

• "Stars and bars: n plus k minus 1 choose k minus 1."
• "Count it twice": double counting.
• "Colour, parity, sum mod m": common invariants.

Summary

Counting uses sum and product rules, stars and bars, inclusion-exclusion and derangements. Proof problems use bijections, double counting, pigeonhole with cleverly chosen boxes, invariants, induction and extremal choices.

Graph facts such as degree sums and trees support many arguments, and game problems are solved from the end position backwards.

Exam protocol

• Test small cases to find the pattern.
• State the boxes, the invariant or the extremal object explicitly.
• Split counts into disjoint, exhaustive cases.
• Check the base case and the step in every induction.