IMO Preparation

The International Mathematical Olympiad (IMO) is the premier mathematics competition for pre-university Students, held annually since 1959. Each participating country sends a team of up to six students.

The competition spans two days, each with a 4.5-hour session containing 3 problems. The six problems are divided by convention:

Each problem is worth 7 marks, for a maximum of 42. A gold medal requires approximately 29+, silver Approximately 22+, and bronze approximately 16+ (thresholds vary by year).

The UK team is selected through a multi-stage process:

1. Senior Mathematical Challenge (SMC): Open entry, multiple choice.
2. BMO Round 1: Top 1000 SMC scorers; 6 problems in 3.5 hours.
3. BMO Round 2: Top 100 BMO 1 scorers; 4 problems in 3.5 hours.
4. IMO training camp: Top 20—30 students attend a residential training camp with problem sessions, lectures, and selection tests.
5. Team selection: The team of 6 is chosen based on camp performance and prior results.

IMO problems require complete, rigorous proofs. The standard of rigour expected is higher than at BMO level. Key features include:

• Non-standard constructions that do not arise from routine application of formulas.
• Multi-step arguments where each step is non-trivial.
• Problems that resist standard approaches and require genuine insight.
• Full generality is often required: a solution must handle all cases, including degenerate ones.

Euler’s totient function $\phi(n)$ counts the integers in $\{1, 2, \ldots, n\}$ that are coprime to $n$. For prime $p$: $\phi(p) = p - 1$. For $n = p_1^{a_1} \cdots p_k^{a_k}$:

\phi(n) = n \prod_{p \mid n}\left(1 - \frac{1}{p}\right)

Euler’s Theorem. If $\gcd(a, n) = 1$ Then $a^{\phi(n)} \equiv 1 \pmod{n}$.

Corollary: the order of $a$ modulo $n$. The smallest positive integer $d$ such that $a^d \equiv 1 \pmod{n}$ Is called the order of $a$ modulo $n$ Denoted \text{ord_n(a). The order divides $\phi(n)$ And more Generally divides any exponent $k$ for which $a^k \equiv 1 \pmod{n}$.

Technique: orders in Diophantine equations. If $a^m \equiv a^n \pmod{p}$ with $\gcd(a, p) = 1$ Then m \equiv n \pmod{\text{ord_p(a)}. This is often more precise than working modulo $p - 1$.

Chinese Remainder Theorem (CRT). If $m_1, \ldots, m_k$ are pairwise coprime, then the system of Congruences $x \equiv a_i \pmod{m_i}$ for $i = 1, \ldots, k$ has a unique solution modulo $M = m_1 \cdots m_k$.

Proof sketch. For $k = 2$: let $M_1 = m_2$, $M_2 = m_1$. Compute $t_1$ such that $M_1 t_1 \equiv 1 \pmod{m_1}$ (using the extended Euclidean algorithm) and $t_2$ such that $M_2 t_2 \equiv 1 \pmod{m_2}$. Then $x = a_1 M_1 t_1 + a_2 M_2 t_2$ satisfies both congruences.

Technique: splitting a problem. Use CRT to reduce a problem modulo $m$ to problems modulo each Prime power dividing $m$. For example, to find all solutions to $x^2 \equiv 1 \pmod{m}$ Solve $x^2 \equiv 1 \pmod{p^a}$ for each prime power in the factorisation of $m$ and combine via CRT.

Definition. An integer $a$ is a quadratic residue modulo $p$ (prime, $p \nmid a$) if $x^2 \equiv a \pmod{p}$ Has a solution.

Euler’s criterion. $a$ is a quadratic residue modulo $p$ if and only if $a^{(p-1)/2} \equiv 1 \pmod{p}$. If $a$ is a non-residue, then $a^{(p-1)/2} \equiv -1 \pmod{p}$.

Legendre symbol. $\left(\frac{a}{p}\right) = 1$ if $a$ is a QR, $-1$ if $a$ is a QNR, and $0$ if $p \mid a$.

Properties. The Legendre symbol is multiplicative: $\left(\frac{ab}{p}\right) = \left(\frac{a}{p}\right)\left(\frac{b}{p}\right)$. The number of QRs modulo $p$ is $(p-1)/2$.

Quadratic reciprocity. For odd primes $p, q$:

\left(\frac{p}{q}\right)\left(\frac{q}{p}\right) = (-1)^{\frac{p-1}{2} \cdot \frac{q-1}{2}}

Supplementary laws.

\left(\frac{-1}{p}\right) = (-1)^{(p-1)/2}, \quad \left(\frac{2}{p}\right) = (-1)^{(p^2-1)/8}

For an odd prime $p$ and integers $a, b$ with $p \mid a - b$ and $p \nmid ab$:

v_p(a^n - b^n) = v_p(a - b) + v_p(n)

For $p = 2$ and $a, b$ both odd with $4 \mid a - b$:

v_2(a^n - b^n) = v_2(a - b) + v_2(a + b) + v_2(n) - 1

Technique: LTE in Diophantine equations. LTE is extremely useful for determining the exact power of A prime dividing an expression. Combined with size bounds, this often forces the only possible solutions.

Ramsey’s theorem (finite version). For any positive integers $r, s$ There exists a smallest integer $R(r, s)$ such that any 2-colouring of the edges of a complete graph on $R(r, s)$ vertices contains Either a red $K_r$ or a blue $K_s$.

Known values and bounds. $R(3, 3) = 6$, $R(3, 4) = 9$, $R(3, 5) = 14$, $R(4, 4) = 18$. $R(r, s) \leq \binom{r+s-2}{r-1}$.

Technique: constructive lower bounds. To show $R(r, s) > n$ Exhibit a 2-colouring of $K_n$ with no Red $K_r$ or blue $K_s$. For $R(3, 3) > 5$: colour the edges of a pentagon red and the diagonals blue.

Technique: induction in Ramsey theory. The recurrence $R(r, s) \leq R(r-1, s) + R(r, s-1)$ follows From considering a single vertex and its red and blue neighbours.

Handshaking lemma. $\sum_{v \in V} \deg(v) = 2|E|$.

Trees. A connected graph on $n$ vertices with $n - 1$ edges is a tree. Equivalently, a graph with No cycles and $n - 1$ edges on $n$ vertices is connected (hence a tree).

Planarity. A graph is planar if it can be drawn in the plane without edge crossings. Euler’s formula For connected planar graphs: $V - E + F = 2$ Where $F$ is the number of faces.

Technique: graph invariants. The chromatic number, independence number, clique number, and Matching number are powerful tools. The pigeonhole principle applied to degrees often yields results.

Technique: Tournaments. A tournament is a complete directed graph. Every tournament has a Hamiltonian Path. A transitive tournament (where the ordering is consistent) has a unique Hamiltonian path.

The probabilistic method proves the existence of an object with certain properties by showing that a Randomly chosen object has a positive probability of having those properties.

Basic form. If the expected number of “bad” events is less than 1, then there exists an outcome With no bad events.

Lovasz Local Lemma. If events $A_1, \ldots, A_n$ each have probability at most $p$ Each event is Independent of all but at most $d$ other events, and $ep(d+1) \leq 1$ Then there is a nonzero Probability that none of the events occur.

Technique: linearity of expectation. The expected value of a sum equals the sum of expected values, Regardless of dependence. This is often combined with the probabilistic method to prove existence of Objects with certain average properties.

Example application. In any graph $G$ with $m$ edges, there exists a bipartite subgraph with at Least $m/2$ edges. Proof: randomly partition the vertices into two sets $A, B$ by assigning each Vertex independently with probability $1/2$. Each edge crosses the partition with probability $1/2$ so the expected number of crossing edges is $m/2$. Therefore some partition achieves at least $m/2$.

Ordinary generating functions (OGF). $G(x) = \sum_{n=0}^{\infty} a_n x^n$. Used for counting problems With additive structure.

Exponential generating functions (EGF). $G_e(x) = \sum_{n=0}^{\infty} a_n \frac{x^n}{n!}$. Used for Counting labelled structures.

Technique: extracting coefficients. The coefficient of $x^n$ in $(1-x)^{-k}$ is $\binom{n+k-1}{k-1}$. The coefficient of $x^n$ in $e^{kx}$ is $k^n/n!$.

Technique: Catalan numbers. $C_n = \frac{1}{n+1}\binom{2n}{n}$ counts triangulations of a convex $(n+2)$-gon, valid parenthesis expressions with $n$ pairs, and many other combinatorial structures. The generating function $C(x) = \sum C_n x^n$ satisfies $C(x) = 1 + xC(x)^2$.

Cauchy-Schwarz (Engel form). For positive reals and real weights:

\frac{a_1^2}{b_1} + \frac{a_2^2}{b_2} + \cdots + \frac{a_n^2}{b_n} \geq \frac{(a_1 + a_2 + \cdots + a_n)^2}{b_1 + b_2 + \cdots + b_n}

This form is particularly useful for olympiad problems because it directly produces the desired Bound without an intermediate step.

Holder’s Inequality. For $a_{ij} > 0$ and $p_1, p_2, \ldots, p_k > 1$ with $1/p_1 + \cdots + 1/p_k = 1$:

\sum_{i=1}^{n}\prod_{j=1}^{k} a_{ij} \leq \prod_{j=1}^{k}\left(\sum_{i=1}^{n} a_{ij}^{p_j}\right)^{1/p_j}

Muirhead’s Inequality. A symmetric sum \sum_{\text{sym} x_1^{a_1} x_2^{a_2} \cdots x_n^{a_n} Is denoted $[a_1, a_2, \ldots, a_n]$. We say $(a_1, \ldots, a_n)$ majorises $(b_1, \ldots, b_n)$ If the sum of the $k$ largest $a_i$ is at least the sum of the $k$ largest $b_i$ for all $k$ With Equality when $k = n$. Muirhead’s inequality states that if $(a)$ majorises $(b)$ and $x_1, \ldots, x_n > 0$ Then $[a] \geq [b]$.

Schur’s Inequality. For $r \geq 0$ and $x, y, z \geq 0$:

x^r(x-y)(x-z) + y^r(y-z)(y-x) + z^r(z-x)(z-y) \geq 0

For $r = 1$: $x^3 + y^3 + z^3 + 3xyz \geq x^2y + x^2z + y^2x + y^2z + z^2x + z^2y$.

Resultant. The resultant of polynomials $P$ and $Q$ is zero if and only if $P$ and $Q$ share a Common root. For $P(x) = a\prod(x - \alpha_i)$ and $Q(x) = b\prod(x - \beta_j)$:

\text{Res(P, Q) = a^m b^n \prod_{i,j}(\alpha_i - \beta_j) = a^m \prod_i Q(\alpha_i) = b^n \prod_j P(\beta_j)

Where $m = \deg P$ and $n = \deg Q$.

Technique: irreducibility. Eisenstein’s criterion: if $f(x) = a_n x^n + \cdots + a_0 \in \mathbb{Z}[x]$ And there exists a prime $p$ such that $p \nmid a_n$, $p \mid a_i$ for $i < n$ And $p^2 \nmid a_0$ Then $f$ is irreducible over $\mathbb{Q}$.

Technique: roots of unity. The $n$-th roots of unity are $\zeta_n^k = e^{2\pi i k/n}$ for $k = 0, 1, \ldots, n-1$. The cyclotomic polynomial $\Phi_n(x) = \prod_{\substack{1 \leq k \leq n \\ \gcd(k,n)=1}}(x - \zeta_n^k)$ Is irreducible over $\mathbb{Q}$ and has degree $\phi(n)$.

Technique: injectivity and surjectivity. Prove that the function is injective (if $f(a) = f(b)$ then $a = b$) or surjective (every value in the codomain is achieved). These properties are often easier to Establish first and then used to unlock further progress.

Technique: iteration. If the equation relates $f(f(x))$ to $f(x)$ or $x$ Iterating can produce A chain of relations: $f^n(x) = f(f^{n-1}(x))$.

Cauchy’s equation over rationals. $f(x + y) = f(x) + f(y)$ for all rational $x, y$. Setting $x = y = 0$ Gives $f(0) = 0$. Setting $y = -x$ gives $f(-x) = -f(x)$. By induction, $f(nx) = nf(x)$ for integers $n$. Setting $x = 1$ and $y = m/n$: $f(m/n) = m \cdot f(1/n)$ and $f(1) = n \cdot f(1/n)$ So $f(m/n) = (m/n) \cdot f(1)$.

Vieta jumping is a technique for solving Diophantine equations of the form $P(x, y) = 0$ where $P$ is symmetric. Given a solution $(x, y)$ with $x \geq y$ One can often Construct a new solution $(x', y)$ with $x' < x$ using Vieta’s formulas, then descend to a minimal Solution and analyse it.

Standard setup. Suppose $x^2 + y^2 + 1 = kxy$ for some fixed positive integer $k$ and positive Integers $x, y$. View this as a quadratic in $x$: $x^2 - (ky)x + (y^2 + 1) = 0$. If $(x, y)$ is a Solution, then by Vieta’s formulas, the other root is $x' = ky - x$. Since $x + x' = ky$ and $xx' = y^2 + 1$ We have $x' = (y^2 + 1)/x$ Which is a positive integer. If $x > y$ Then $x' = (y^2 + 1)/x < (x^2 + 1)/x = x + 1/x < x + 1$ So $x' \leq x$. If $x > y$ Then $x' < x$ Giving a descent.

Inversion about a circle. Given a circle $\omega$ with centre $O$ and radius $r$ The inversion of a Point $P \neq O$ is the point $P'$ on ray $OP$ such that $OP \cdot OP' = r^2$. Points on $\omega$ are Fixed.

Properties.

• Inversion preserves angles (it is a conformal map).
• A line not through $O$ inverts to a circle through $O$ And vice versa.
• A circle not through $O$ inverts to another circle not through $O$.
• The image of a circle through $O$ is a line not through $O$ (perpendicular to the line through $O$ and the centre of the original circle).

Technique: inverting a configuration. When a problem involves several circles passing through a Common point, inverting about that point often simplifies the configuration by turning circles into Lines. For problems with two tangent circles, inverting about the point of tangency turns both Circles into parallel lines.

Technique: preserving tangency and intersection. If two curves are tangent at a point (other Than $O$), their images are also tangent at the image point. If two curves intersect, their images also intersect.

Projective transformations preserve collinearity and cross-ratios. Any four points Position (no three collinear) can be mapped to any other four points position by a unique Projective transformation.

Cross-ratio. For four collinear points $A, B, C, D$:

(A, B; C, D) = \frac{AC \cdot BD}{AD \cdot BC}

This is invariant under projective transformations.

Technique: sending points to infinity. A projective transformation can send any line to the Line at infinity. This turns a configuration involving parallel lines or ratios into a simpler one.

Harmonic division. Four collinear points $A, B, C, D$ form a harmonic range if $(A,B;C,D) = -1$. This occurs, for instance, when $C$ and $D$ are the intersections of a line with a complete quadrilateral.

Setup. Place the circumcircle of $\triangle ABC$ on the unit circle in $\mathbb{C}$. Then the Vertices correspond to complex numbers $a, b, c$ with $|a| = |b| = |c| = 1$.

Key formulas. With $a, b, c$ on the unit circle ($\bar{a} = 1/a$ Etc.):

• Centroid: $g = (a + b + c)/3$
• Orthocentre: $h = a + b + c$
• Circumcentre: $o = 0$
• Nine-point centre: $n = (a + b + c)/2$

Collinearity. Points $p, q, r$ are collinear if and only if $\frac{p - q}{p - r} \in \mathbb{R}$.

Perpendicularity. Lines $PQ$ and $RS$ are perpendicular if and only if $\frac{p - q}{r - s} \in i\mathbb{R}$.

Technique: the foot of the perpendicular. The foot of the perpendicular from $P$ to line $AB$ (where $a, b$ are on the unit circle) is:

f = \frac{a + b + p - ab\bar{p}}{2}

Setup. For a reference triangle $ABC$ Any point $P$ has barycentric coordinates $(x : y : z)$ Where $x + y + z \neq 0$ and $P$ is the weighted average $P = \frac{xA + yB + zC}{x + y + z}$.

Key points.

• $A = (1:0:0)$, $B = (0:1:0)$, $C = (0:0:1)$
• Centroid $G = (1:1:1)$
• Incentre $I = (a:b:c)$ where $a, b, c$ are side lengths
• Circumcentre $O = (a^2(b^2 + c^2 - a^2) : b^2(c^2 + a^2 - b^2) : c^2(a^2 + b^2 - c^2))$

Collinearity. Three points $(x_1:y_1:z_1)$, $(x_2:y_2:z_2)$, $(x_3:y_3:z_3)$ are collinear if And only if:

\begin{vmatrix} x_1 & y_1 & z_1 \ x_2 & y_2 & z_2 \ x_3 & y_3 & z_3 \end{vmatrix} = 0

Concyclicity. A point $P = (x:y:z)$ lies on the circumcircle of $ABC$ if and only if $a^2yz + b^2zx + c^2xy = 0$.

Let $a$ and $b$ be positive integers such that $ab + 1$ divides $a^2 + b^2$. Prove that $\frac{a^2 + b^2}{ab + 1}$ is a perfect square.

Solution. Let $k = \frac{a^2 + b^2}{ab + 1}$. We need to show $k$ is a perfect square. Note that $k$ is a positive integer. Suppose for contradiction that $k$ is not a perfect square.

Without loss of generality, assume $a \geq b > 0$. Consider all pairs $(a, b)$ of positive integers with $a \geq b$ such that $\frac{a^2 + b^2}{ab + 1} = k$ (the same $k$). Among all such pairs, Choose one with $a + b$ minimal.

From $a^2 + b^2 = k(ab + 1)$ View this as a quadratic in $a$: $a^2 - kba + (b^2 - k) = 0$. By Vieta’s formulas, if $a$ is one root, the other root is $a' = kb - a$ with $aa' = b^2 - k$.

Since $a \geq b > 0$ and $k \geq 1$ We have $a' = kb - a$. Also, $a' = (b^2 - k)/a$.

Claim: $a' \geq 0$ and $(a', b)$ is also a valid pair with the same $k$.

First, if $a' < 0$ then $b^2 < k$. But then $k = (a^2 + b^2)/(ab+1) < (a^2 + k)/(ab+1)$ Giving $kab < a^2$ So $kb < a$. But $a' = kb - a < 0$ is consistent with this. In this case, we have $b^2 < k$ and $a > kb$. Since $a$ is the larger root of the quadratic, $a = (kb + \sqrt{D})/2 > kb/2$. If $kb < a$ Then $a' = kb - a < 0$.

If $a' = 0$: then $b^2 = k$ So $k$ is a perfect square, contradicting our assumption.

If $a' > 0$: then $(a', b)$ is a valid pair (by Vieta, $a'^2 + b^2 = k(a'b + 1)$) with $a' + b < a + b$ (since $a' = kb - a < a$ because $a = (kb + \sqrt{D})/2 > kb/2$ implies $kb - a < kb - kb/2 = kb/2 < a$). This contradicts the minimality of $a + b$.

The only remaining possibility is that no valid pair exists with $k$ not a perfect square, which Means $k$ must be a perfect square.

A graph $G$ on $n$ vertices has no cycles of length 3 (i.e., $G$ is triangle-free). Prove that $G$ has at most $\lfloor n^2/4 \rfloor$ edges.

Solution. Let $d_v$ denote the degree of vertex $v$ And let $m = |E|$ be the number of edges.

For any edge $uv$ Since $G$ is triangle-free, no neighbour of $u$ is adjacent to $v$. Therefore $d_u + d_v \leq n$ (the $d_u$ neighbours of $u$ and $d_v$ neighbours of $v$ are all distinct, plus $u$ and $v$ themselves give at most $n$ vertices).

Summing over all edges:

\sum_{uv \in E}(d_u + d_v) \leq mn

The left side equals $\sum_{v \in V} d_v^2$ (each vertex $v$ contributes $d_v$ to each of its $d_v$ incident edges).

By Cauchy-Schwarz:

\sum_v d_v^2 \geq \frac{\left(\sum_v d_v\right)^2}{n} = \frac{(2m)^2}{n} = \frac{4m^2}{n}

Combining: $4m^2/n \leq mn$ So $4m \leq n^2$ Giving $m \leq n^2/4$.

Since $m$ is an integer, $m \leq \lfloor n^2/4 \rfloor$.

Equality holds when all $d_v = n/2$ (from Cauchy-Schwarz equality) and $d_u + d_v = n$ for every edge. This is achieved by the complete bipartite graph $K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil}$.

Prove that for all positive real numbers $a, b, c$:

$$$$

Solution. By Titu’s lemma (the Engel form of Cauchy-Schwarz):

\sum \frac{a^3}{b^2 - bc + c^2} = \sum \frac{a^4}{a(b^2 - bc + c^2)} \geq \frac{(a^2 + b^2 + c^2)^2}{\sum a(b^2 - bc + c^2)}

\sum a(b^2 - bc + c^2) = \sum_{\text{sym} a^2 b - 3abc

\frac{(a^2 + b^2 + c^2)^2}{\sum_{\text{sym} a^2 b - 3abc} \geq a + b + c

\sum a^4 + 2\sum a^2 b^2 \geq \sum_{\text{sym} a^3 b - \sum a^2 bc