Maths olympiad roadmap.

A statement of the form if $P$ then $Q$ (written $P \Rightarrow Q$) is proved by assuming $P$ and deducing $Q$ in steps that each follow from the last. Three related statements are easy to confuse:

• The converse $Q \Rightarrow P$ is a different statement. It may be false even when the original is true.
• The contrapositive $\text{not } Q \Rightarrow \text{not } P$ is logically the same as the original. Proving it is often easier.
• If and only if ($P \Leftrightarrow Q$) needs two proofs: one in each direction.

Watch the quantifiers. "For all $n$" needs an argument that works for every $n$; checking examples is not enough. "There exists $n$" needs one example, shown to work. To disprove a "for all" claim, one counterexample is enough.

Write integers in a form that carries the hypothesis: an even number is $2k$, an odd number is $2k+1$, a multiple of 3 is $3k$, where $k$ is an integer. Then let the algebra do the work, and finish with a sentence that states what you have shown.

To prove a statement $S(n)$ for all integers $n \ge n_0$:

1. Base case. Show $S(n_0)$ is true.
2. Inductive step. Assume $S(k)$ is true for some $k \ge n_0$ (the inductive hypothesis) and deduce $S(k+1)$.
3. Conclusion. Say that by induction $S(n)$ holds for all $n \ge n_0$.

The key moment is where you use the hypothesis. Write $S(k+1)$ in a way that makes $S(k)$ appear inside it, for example by splitting off the last term of a sum or by factoring.

Strong induction lets you assume $S(n_0), S(n_0+1), \dots, S(k)$ all hold. Use it when $S(k+1)$ depends on more than the case just before, as with recurrences such as $a_{n+2} = a_{n+1} + a_n$. You then need as many base cases as the step reaches back.

Common errors: forgetting the base case, proving the step only for large $k$ while the base is small, and assuming what you want to prove. Sometimes a stronger statement is easier to prove by induction, because the hypothesis gives you more to work with.

To prove $P$ by contradiction, assume not $P$ and reason until you reach a statement that is clearly false, such as $1 = 0$, an odd number equal to an even one, or a positive integer smaller than the smallest one. Then not $P$ is impossible, so $P$ is true.

Two classic models to know:

• $\sqrt{2}$ is irrational: suppose $\sqrt{2} = p/q$ in lowest terms; then $p^2 = 2q^2$, so $p$ is even, then $q$ is even, contradicting lowest terms.
• There are infinitely many primes: suppose $p_1, \dots, p_m$ are all of them; then $p_1 p_2 \cdots p_m + 1$ has a prime factor that is none of them.

Good habits: state clearly at the start "Suppose, for contradiction, that ...". Write down exactly what the assumption gives you as equations or inequalities. Parity, divisibility and size (one side too big) are the most common sources of the contradiction. At the end, say which fact is contradicted.

Contradiction is close to the contrapositive. If your argument only uses the assumption to get a single implication, a contrapositive proof may be cleaner.

Many problems become easier if you pick the object that is biggest or smallest in some sense: the longest side, the point furthest from a line, the team with most wins, the smallest solution. Every finite set of real numbers has a largest and a smallest element, and every non-empty set of positive integers has a smallest element (the well-ordering principle).

The usual pattern is:

1. Choose an extreme object $X$.
2. Suppose the result fails for $X$.
3. Build a new object $Y$ that is even more extreme than $X$, a contradiction.

Infinite descent is the number theory version. To show an equation has no positive integer solutions, take the solution with the smallest value of some positive integer quantity, then construct a solution with a smaller value. Since positive integers cannot decrease for ever, there was no solution at all.

Ask yourself in every problem: what is the natural "size" here, and what happens if I look at the largest or smallest one?

Basic form. If $n + 1$ objects are placed in $n$ boxes, some box contains at least two objects.

General form. If $N$ objects are placed in $n$ boxes, some box contains at least $\lceil N/n \rceil$ objects. For example, $kn + 1$ objects in $n$ boxes force some box to hold $k + 1$.

The statement is easy; the art is in choosing the boxes. Common choices:

• Remainders on division by $m$: among $m + 1$ integers, two have the same remainder, so their difference is divisible by $m$.
• Pairs that sum to a fixed total, such as $\{1, 99\}, \{2, 98\}, \dots$
• Regions of a shape: split a square into smaller squares and look for two points in one piece.
• Chains or classes, such as numbers with the same odd part.

When you write it up, name the boxes, say how many objects and boxes there are, and state what two objects in one box gives you. A good sign you need pigeonhole: the problem says "prove that two of them ..." or "prove that some ..." without asking which.

A problem describes a starting state and a move that can be repeated. You are asked whether a final state can be reached, or whether the process must stop.

An invariant is a quantity that every move leaves unchanged. If the invariant has different values at the start and at the target, the target can never be reached. Useful candidates:

• parity (odd or even) of a sum or of a count;
• a remainder on division by some $m$;
• a sum, product or sum of squares;
• a colouring count, such as how many black squares a piece covers.

A monovariant is a quantity that changes in one direction only: it strictly increases (or decreases) with every move. If it is a positive integer that strictly decreases, the process must stop after finitely many moves.

How to find one: try a few moves by hand and record simple quantities (sum, parity, sum of squares) before and after. Write the effect of one general move algebraically, and check what stays the same. In the write-up, prove the invariant property for a general move, then compare start and target.

For non-negative reals $a_1, a_2, \dots, a_n$:

with equality if and only if all the $a_i$ are equal.

The two-variable case comes from a square: $(\sqrt{a} - \sqrt{b})^2 \ge 0$ expands to $a + b \ge 2\sqrt{ab}$. Know the useful special case $x + \dfrac{1}{x} \ge 2$ for $x \gt 0$.

How to use it:

• Minimising a sum. Split the sum into terms whose product is constant. Then AM-GM gives a lower bound.
• Maximising a product. Arrange factors whose sum is constant.
• Check equality. A bound is only the minimum if the equality case can actually happen. Find the values where all terms are equal and check they satisfy the conditions.
• Add several AM-GMs. For symmetric inequalities, apply two-variable AM-GM to each pair and add, or multiply, the results.

Splitting a term into equal parts (writing $2x$ as $x + x$) is the most common trick for making the product constant.

Cauchy-Schwarz. For reals $a_1, \dots, a_n$ and $b_1, \dots, b_n$:

with equality when the two lists are proportional ($a_i = \lambda b_i$ for all $i$). In vector language it says $|\mathbf{a} \cdot \mathbf{b}| \le |\mathbf{a}||\mathbf{b}|$, which you know from the scalar product.

Fraction form (Titu's lemma). For reals $x_i$ and positive $y_i$:

Power means. For positive reals, quadratic mean $\ge$ arithmetic mean $\ge$ geometric mean $\ge$ harmonic mean:

Use Cauchy-Schwarz when a constraint is linear and the target is a sum of squares, or the reverse. Use Titu when you see a sum of fractions with squares (or constants you can write as squares) on top. As with AM-GM, always find the equality case: it tells you whether the bound is the answer.

A linear recurrence of order 2 has the form $a_{n+2} = p\,a_{n+1} + q\,a_n$ with constants $p, q$, and two starting values $a_0, a_1$.

Try $a_n = r^n$. Dividing by $r^n$ gives the characteristic equation

• Two different roots $r_1, r_2$: every solution is $a_n = A r_1^n + B r_2^n$.
• A repeated root $r$: every solution is $a_n = (A + Bn)\,r^n$.

Find $A$ and $B$ from the two starting values. Always check your formula on the next term.

This also explains power sums: if $\alpha, \beta$ are the roots of $x^2 = px + q$, then $s_n = \alpha^n + \beta^n$ satisfies $s_{n+2} = p\,s_{n+1} + q\,s_n$. So you can compute $\alpha^{10} + \beta^{10}$ step by step from $s_0 = 2$ and $s_1 = p$.

A geometric progression is the order-1 case: $a_{n+1} = r a_n$ gives $a_n = a_0 r^n$. For $a_{n+1} = r a_n + c$, add a constant to make it geometric: find $k$ with $k = rk + c$, then $a_n - k$ is geometric.

A functional equation asks for all functions $f$ (say from $\mathbb{R}$ to $\mathbb{R}$) satisfying a rule for all inputs. A full answer has two parts: show that any solution must be one of a list, and check that every function in the list really works.

Opening moves:

• Substitute special values: $x = 0$, $y = 0$, $y = x$, $y = -x$, $x = 1$. Each gives a fact such as the value of $f(0)$.
• Swap or replace variables: replacing $x$ by $1 - x$ or $y$ by $x$ can give a second equation; then solve the pair like simultaneous equations.
• Injectivity ($f(a) = f(b) \Rightarrow a = b$) and surjectivity (every value is taken) let you cancel $f$ or substitute any value.
• Guess the answer early by trying $f(x) = cx$ or $f(x) = cx + d$. Knowing the target guides your substitutions.

Know Cauchy's equation $f(x + y) = f(x) + f(y)$: over the rationals its only solutions are $f(x) = cx$; over the reals you need an extra condition (for example $f$ monotonic or continuous) to reach the same answer.

Common error: finding $f(x) = x$ from one substitution and stopping. A substitution gives necessary conditions only; you still need to show nothing else works and that your answer satisfies the original equation.

Write $a \mid b$ for "$a$ divides $b$". The key fact: if $d \mid a$ and $d \mid b$, then $d \mid ax + by$ for any integers $x, y$.

So $\gcd(a, b) = \gcd(a - kb, b)$ for any integer $k$. Repeating this with division gives Euclid's algorithm: divide, keep the remainder, and repeat until the remainder is 0. The last non-zero remainder is the gcd.

Bezout's identity. For integers $a, b$ not both zero, there are integers $x, y$ with

You find $x, y$ by running Euclid's algorithm backwards. A consequence: $\gcd(a, b) = 1$ exactly when some combination $ax + by$ equals 1.

Two results that follow and are used constantly:

• If $\gcd(a, b) = 1$ and $a \mid bc$, then $a \mid c$.
• If $p$ is prime and $p \mid bc$, then $p \mid b$ or $p \mid c$.

For expressions in $n$, use the "subtract a multiple" step algebraically. For example, $\gcd(2n + 3, n + 1) = \gcd(1, n + 1) = 1$, since $2n + 3 - 2(n + 1) = 1$.

Write $a \equiv b \pmod{m}$ when $m \mid a - b$, that is, $a$ and $b$ leave the same remainder on division by $m$.

Congruences can be added, subtracted and multiplied like equations: if $a \equiv b$ and $c \equiv d \pmod m$, then $a + c \equiv b + d$ and $ac \equiv bd \pmod m$. So you may replace any number by its remainder before you calculate, and $a \equiv b$ gives $a^k \equiv b^k$.

Division needs care. You can cancel a factor $c$ from both sides only when $\gcd(c, m) = 1$. For example $2 \times 3 \equiv 2 \times 0 \pmod 6$ but $3 \not\equiv 0$.

Powers cycle. The remainders of $a, a^2, a^3, \dots$ modulo $m$ eventually repeat. List them until they do, then use the cycle length.

Squares modulo small numbers are worth memorising:

• squares mod 3 and mod 4: $0, 1$
• squares mod 5: $0, 1, 4$; squares mod 8: $0, 1, 4$
• cubes mod 9: $0, 1, 8$

To show an equation has no integer solutions, reduce both sides modulo a well-chosen $m$ and show the remainders can never match. Good moduli: 3, 4, 8, 9, or a prime that appears in the problem.

Fermat's little theorem. If $p$ is prime and $p \nmid a$, then

Equivalently, $a^p \equiv a \pmod p$ for every integer $a$.

Euler's totient $\varphi(m)$ counts the integers from 1 to $m$ that are coprime to $m$. For $m = p_1^{k_1} \cdots p_r^{k_r}$,

For example $\varphi(100) = 100 \times \tfrac12 \times \tfrac45 = 40$.

Euler's theorem. If $\gcd(a, m) = 1$, then $a^{\varphi(m)} \equiv 1 \pmod m$. Fermat is the case $m = p$.

To reduce $a^N \bmod m$: divide $N$ by $\varphi(m)$ (or $p - 1$) and keep only the remainder as the new exponent. Check the coprime condition first.

Order. The smallest $d \ge 1$ with $a^d \equiv 1 \pmod m$ is the order of $a$. A key fact: $a^N \equiv 1 \pmod m$ exactly when the order divides $N$; in particular the order divides $\varphi(m)$. Arguments with the order are the standard way to show that a prime dividing $a^n - 1$ must have a special form.

Also worth knowing: Wilson's theorem, $(p - 1)! \equiv -1 \pmod p$ for a prime $p$.

For a prime $p$, write $v_p(n)$ for the exponent of $p$ in $n$: the largest $k$ with $p^k \mid n$. So $v_2(40) = 3$ and $v_5(40) = 1$. It behaves like a logarithm: $v_p(ab) = v_p(a) + v_p(b)$, and $v_p(a + b) \ge \min(v_p(a), v_p(b))$.

Legendre's formula. The exponent of $p$ in $n!$ is

The first term counts multiples of $p$, the second counts the extra factor in multiples of $p^2$, and so on.

Lifting the exponent (odd prime). Let $p$ be an odd prime with $p \mid x - y$, and $p \nmid x$, $p \nmid y$. Then for every positive integer $n$:

For odd $n$ there is a matching form for sums: if $p \mid x + y$ then $v_p(x^n + y^n) = v_p(x + y) + v_p(n)$.

The prime 2 behaves differently. For odd $x, y$ and even $n$: $v_2(x^n - y^n) = v_2(x - y) + v_2(x + y) + v_2(n) - 1$. Do not apply the odd-prime form when $p = 2$.

In a write-up, quote the lemma by name and check its conditions in one line.

A Diophantine equation asks for integer (or positive integer) solutions. Four tools solve most olympiad examples:

1. Factorise. Rearrange so one side is a product and the other a fixed number, then list the factor pairs. Expressions like $xy + ax + by$ factorise after adding a constant: $xy + ax + by + ab = (x + b)(y + a)$. This is Simon's favourite factoring trick.
2. Work modulo $m$. If the two sides can never have the same remainder modulo some $m$, there are no solutions. Squares and cubes have few remainders, so moduli 3, 4, 8 and 9 are good first tries.
3. Bound. Show the variables must be small (for example, assume $x \le y$ and show $x \le 3$), then check the few cases left. Inequalities between consecutive squares help: no square lies strictly between $k^2$ and $(k + 1)^2$.
4. Linear equations $ax + by = c$ have integer solutions exactly when $\gcd(a, b) \mid c$. From one solution $(x_0, y_0)$, all are $x = x_0 + \frac{b}{d}t$, $y = y_0 - \frac{a}{d}t$ with $d = \gcd(a, b)$.

Also meet Pell's equation $x^2 - dy^2 = 1$, which has infinitely many solutions when $d$ is a positive non-square.

A complete answer lists every solution and shows there are no others. Watch for negative factor pairs and for solutions where a variable is 0.

A bijection is a pairing between two sets in which every element of each set is matched with exactly one element of the other. If you find one, the two sets have the same size. In a proof you should describe the map in both directions, or show it is one-to-one and covers everything.

Stars and bars. The number of solutions of $x_1 + x_2 + \cdots + x_k = n$ in non-negative integers is

Each solution matches a row of $n$ stars and $k - 1$ bars: the bars cut the stars into $k$ groups. For positive integers, the count is $\binom{n - 1}{k - 1}$ (choose $k - 1$ of the $n - 1$ gaps between stars).

Lattice paths. A path of right and up steps from $(0, 0)$ to $(a, b)$ is a word of $a$ R's and $b$ U's, so there are $\binom{a + b}{a}$ paths.

Double counting. Count the same set in two different ways and set the answers equal. For example, counting pairs (person, handshake) gives the handshake lemma, and counting committees with a chair two ways gives $k\binom{n}{k} = n\binom{n - 1}{k - 1}$.

When you are stuck on a count, compute the first few values. If you recognise the sequence (powers of 2, binomial coefficients, Fibonacci, Catalan numbers), look for the bijection that explains it.

A graph is a set of vertices with some pairs joined by edges. The degree of a vertex is the number of edges at it.

Facts to know and be able to prove:

• Handshake lemma. The sum of all degrees is twice the number of edges. So the number of odd-degree vertices is even.
• Trees. A connected graph with no cycles is a tree. A tree with $n$ vertices has exactly $n - 1$ edges, and every tree with at least 2 vertices has a vertex of degree 1 (a leaf), which is good for induction.
• Euler circuits. A connected graph has a closed walk using every edge exactly once if and only if every vertex has even degree.
• Bipartite graphs. The vertices split into two groups with every edge going between the groups exactly when the graph has no cycle of odd length.
• Ramsey. Among any 6 people there are 3 who all know each other or 3 who are all strangers. Proof: pick one person; of the other 5, at least 3 are in the same relation to them (pigeonhole), and look at those 3.

In a problem, decide what the vertices and edges are, then ask what degrees, paths or cycles tell you. Draw small cases; graphs are easy to sketch.

In these games two players move in turn, both know everything, there is no luck, and the game must end. One player has a winning strategy, and the task is to say who and prove it.

Winning and losing positions. Call a position losing (for the player about to move) if every move leads to a winning position, and winning if some move leads to a losing position. The end position, where no move is possible, is usually losing. Work backwards from small positions, list which are losing, guess the pattern, then prove it:

• from every losing position, every move goes to a winning one;
• from every winning position, some move goes to a losing one.

Symmetry (copycat) strategy. In symmetric positions, the second player can often copy the first player's move in a mirror image, so the second player always has a move. On a board, the first player may instead make one central move and then copy.

Strategy stealing. Sometimes you can prove the first player wins without finding the strategy: if the second player had a winning strategy, the first player could make a harmless move and then use it.

Know the game of Nim: with several piles, the player to move loses exactly when the binary XOR of the pile sizes is 0.

Take a circle with centre $O$, radius $r$, and a point $P$. Draw any line through $P$ meeting the circle at $A$ and $B$. Then the product $PA \cdot PB$ is the same for every such line. This constant is the power of $P$:

• $P$ inside (intersecting chords): if chords $AB$ and $CD$ meet at $P$, then $PA \cdot PB = PC \cdot PD$.
• $P$ outside (secants): $PA \cdot PB = PC \cdot PD$ for two lines through $P$.
• Tangent: if $PT$ touches the circle at $T$, then $PT^2 = PA \cdot PB$.

Each result comes from a pair of similar triangles, for example $\triangle PAC \sim \triangle PDB$, so you can always prove it again if needed.

The converse is a test for concyclic points: if lines $AB$ and $CD$ meet at $P$ and $PA \cdot PB = PC \cdot PD$ (with signs matching), then $A, B, C, D$ are concyclic.

Radical axis. The points with equal power with respect to two circles form a straight line, perpendicular to the line of centres. If the circles meet, it is the line through the two meeting points. For three circles, the three radical axes are concurrent (or parallel). This is a standard way to prove three lines meet at a point.

Take triangle $ABC$ with points $D$ on line $BC$, $E$ on line $CA$ and $F$ on line $AB$.

Ceva's theorem. With $D, E, F$ on the sides themselves, the lines $AD$, $BE$, $CF$ meet at one point if and only if

Go round the triangle in order: $B \to D \to C \to E \to A \to F \to B$. This proves at once that the medians, the angle bisectors and the altitudes are concurrent. For angle bisectors, use the angle bisector theorem $BD/DC = AB/AC$.

Menelaus' theorem. Points $D, E, F$ (one or three of them on extended sides) are collinear if and only if the same product, with unsigned lengths, equals 1:

With signed lengths the Ceva product is $+1$ and the Menelaus product is $-1$; this is what tells the two situations apart.

Trigonometric Ceva. $AD, BE, CF$ are concurrent if and only if $\dfrac{\sin \angle BAD}{\sin \angle DAC} \cdot \dfrac{\sin \angle CBE}{\sin \angle EBA} \cdot \dfrac{\sin \angle ACF}{\sin \angle FCB} = 1$. Use it when you know angles rather than lengths.

Use Menelaus when a line cuts across a triangle and you want a ratio on a side; choose the triangle and the transversal carefully.