International Mathematical Olympiad

A hunter and an invisible rabbit play a game in the Euclidean plane. The rabbit's starting point, $A_0$, and the hunter's starting point, $B_0$, are the same. After $n - 1$ rounds of the game, the rabbit is at point $A_{n-1}$ and the hunter is at point $B_{n-1}$. In the $n^{\text{th}}$ round of the game, three things occur in order.

(i) The rabbit moves invisibly to a point $A_{n}$ such that the distance between $A_{n-1}$ and $A_{n}$ is exactly 1.

(ii) A tracking device reports a point $P_{n}$ to the hunter. The only guarantee provided by the tracking device to the hunter is that the distance between $P_{n}$ and $A_{n}$ is at most 1.

(iii) The hunter moves visibly to a point $B_{n}$ such that the distance between $B_{n-1}$ and $B_{n}$ is exactly 1.

Is it always possible, no matter how the rabbit moves, and no matter what points are reported by the tracking device, for the hunter to choose her moves so that after $10^9$ rounds she can ensure that the distance between her and the rabbit is at most 100?

Let $R$ and $S$ be different points on a circle $\Omega$ such that $RS$ is not a diameter. Let $\ell$ be the tangent line to $\Omega$ at $R$. Point $T$ is such that $S$ is the midpoint of the line segment $RT$. Point $J$ is chosen on the shorter arc $RS$ of $\Omega$ so that the circumcircle $\Gamma$ of triangle $JST$ intersects $\ell$ at two distinct points. Let $A$ be the common point of $\Gamma$ and $\ell$ that is closer to $R$. Line $AJ$ meets $\Omega$ again at $K$. Prove that the line $KT$ is tangent to $\Gamma$.

An integer $N \geqslant 2$ is given. A collection of $N(N + 1)$ soccer players, no two of whom are of the same height, stand in a row. Sir Alex wants to remove $N(N - 1)$ players from this row leaving a new row of $2N$ players in which the following $N$ conditions hold:

(1) no one stands between the two tallest players,

(2) no one stands between the third and fourth tallest players,

$\vdots$

$(N)$ no one stands between the two shortest players.

Show that this is always possible.

An ordered pair $(x, y)$ of integers is a primitive point if the greatest common divisor of $x$ and $y$ is 1. Given a finite set $S$ of primitive points, prove that there exist a positive integer $n$ and integers $a_0, a_1, \ldots, a_n$ such that, for each $(x, y)$ in $S$, we have:

$$a_0 x^n + a_1 x^{n-1} y + a_2 x^{n-2} y^2 + \cdots + a_{n-1} x y^{n-1} + a_n y^n = 1.$$

Triangle $BCF$ has a right angle at $B$. Let $A$ be the point on line $CF$ such that $FA = FB$ and $F$ lies between $A$ and $C$. Point $D$ is chosen such that $DA = DC$ and $AC$ is the bisector of $\angle DAB$. Point $E$ is chosen such that $EA = ED$ and $AD$ is the bisector of $\angle EAC$. Let $M$ be the midpoint of $CF$. Let $X$ be the point such that $AMXE$ is a parallelogram (where $AM \parallel EX$ and $AE \parallel MX$). Prove that lines $BD$, $FX$, and $ME$ are concurrent.

Find all positive integers $n$ for which each cell of an $n \times n$ table can be filled with one of the letters $I$, $M$ and $O$ in such a way that:

• in each row and each column, one third of the entries are $I$, one third are $M$ and one third are $O$; and
• in any diagonal, if the number of entries on the diagonal is a multiple of three, then one third of the entries are $I$, one third are $M$ and one third are $O$.

Note: The rows and columns of an $n \times n$ table are each labelled 1 to $n$ in a natural order. Thus each cell corresponds to a pair of positive integers $(i,j)$ with $1 \leq i,j \leq n$. For $n > 1$, the table has $4n - 2$ diagonals of two types. A diagonal of the first type consists of all cells $(i,j)$ for which $i + j$ is a constant, and a diagonal of the second type consists of all cells $(i,j)$ for which $i - j$ is a constant.

Let $P = A_1A_2\ldots A_k$ be a convex polygon in the plane. The vertices $A_1, A_2, \ldots, A_k$ have integral coordinates and lie on a circle. Let $S$ be the area of $P$. An odd positive integer $n$ is given such that the squares of the side lengths of $P$ are integers divisible by $n$. Prove that $2S$ is an integer divisible by $n$.

A set of positive integers is called fragrant if it contains at least two elements and each of its elements has a prime factor in common with at least one of the other elements. Let $P(n) = n^2 + n + 1$. What is the least possible value of the positive integer $b$ such that there exists a non-negative integer $a$ for which the set $$\{P(a + 1), P(a + 2), \ldots, P(a + b)\}$$ is fragrant?

The equation $$(x - 1)(x - 2) \cdots (x - 2016) = (x - 1)(x - 2) \cdots (x - 2016)$$ is written on the board, with 2016 linear factors on each side. What is the least possible value of $k$ for which it is possible to erase exactly $k$ of these 4032 linear factors so that at least one factor remains on each side and the resulting equation has no real solutions?

There are $n \geq 2$ line segments in the plane such that every two segments cross, and no three segments meet at a point. Geoff has to choose an endpoint of each segment and place a frog on it, facing the other endpoint. Then he will clap his hands $n - 1$ times. Every time he claps, each frog will immediately jump forward to the next intersection point on its segment. Frogs never change the direction of their jumps. Geoff wishes to place the frogs in such a way that no two of them will ever occupy the same intersection point at the same time.

(a) Prove that Geoff can always fulfil his wish if $n$ is odd.

(b) Prove that Geoff can never fulfil his wish if $n$ is even.

We say that a finite set $\mathcal{S}$ of points in the plane is balanced if, for any two different points $A$ and $B$ in $\mathcal{S}$, there is a point $C$ in $\mathcal{S}$ such that $AC = BC$. We say that $\mathcal{S}$ is centre-free if for any three different points $A$, $B$ and $C$ in $\mathcal{S}$, there is no point $P$ in $\mathcal{S}$ such that $PA = PB = PC$.

(a) Show that for all integers $n \geqslant 3$, there exists a balanced set consisting of $n$ points.

(b) Determine all integers $n \geqslant 3$ for which there exists a balanced centre-free set consisting of $n$ points.

Determine all triples $(a, b, c)$ of positive integers such that each of the numbers $$ab - c, \quad bc - a, \quad ca - b$$ is a power of 2.

(A power of 2 is an integer of the form $2^n$, where $n$ is a non-negative integer.)

Let $ABC$ be an acute triangle with $AB > AC$. Let $\Gamma$ be its circumcircle, $H$ its orthocentre, and $F$ the foot of the altitude from $A$. Let $M$ be the midpoint of $BC$. Let $Q$ be the point on $\Gamma$ such that $\angle HQA = 90°$, and let $K$ be the point on $\Gamma$ such that $\angle HKQ = 90°$. Assume that the points $A$, $B$, $C$, $K$ and $Q$ are all different, and lie on $\Gamma$ in this order.

Prove that the circumcircles of triangles $KQH$ and $FKM$ are tangent to each other.

Triangle $ABC$ has circumcircle $\Omega$ and circumcentre $O$. A circle $\Gamma$ with centre $A$ intersects the segment $BC$ at points $D$ and $E$, such that $B$, $D$, $E$ and $C$ are all different and lie on line $BC$ in this order. Let $F$ and $G$ be the points of intersection of $\Gamma$ and $\Omega$, such that $A$, $F$, $B$, $C$ and $G$ lie on $\Omega$ in this order. Let $K$ be the second point of intersection of the circumcircle of triangle $BDF$ and the segment $AB$. Let $L$ be the second point of intersection of the circumcircle of triangle $CGE$ and the segment $CA$.

Suppose that the lines $FK$ and $GL$ are different and intersect at the point $X$. Prove that $X$ lies on the line $AO$.

Let $\mathbb{R}$ be the set of real numbers. Determine all functions $f \colon \mathbb{R} \to \mathbb{R}$ satisfying the equation $$f \big (x + f (x + y) \big) + f (xy) = x + f (x + y) + yf (x)$$ for all real numbers $x$ and $y$.

The sequence $a_1, a_2, \ldots$ of integers satisfies the following conditions:

(i) $1 \leqslant a_{j} \leqslant 2015$ for all $j \geqslant 1$;

(ii) $k + a_{k} \neq \ell + a_{\ell}$ for all $1 \leqslant k < \ell$.

Prove that there exist two positive integers $b$ and $N$ such that $$\left| \sum_{j = m + 1}^{n} (a_{j} - b) \right| \leqslant 1007^{2}$$ for all integers $m$ and $n$ satisfying $n > m \geqslant N$.

Let $a_0 < a_1 < a_2 < \cdots$ be an infinite sequence of positive integers. Prove that there exists a unique integer $n \geq 1$ such that $$a_n < \frac{a_0 + a_1 + \cdots + a_n}{n} \leq a_{n+1}.$$

Let $n \geq 2$ be an integer. Consider an $n \times n$ chessboard consisting of $n^2$ unit squares. A configuration of $n$ rooks on this board is peaceful if every row and every column contains exactly one rook. Find the greatest positive integer $k$ such that, for each peaceful configuration of $n$ rooks, there is a $k \times k$ square which does not contain a rook on any of its $k^2$ unit squares.

Convex quadrilateral $ABCD$ has $\angle ABC = \angle CDA = 90°$. Point $H$ is the foot of the perpendicular from $A$ to $BD$. Points $S$ and $T$ lie on sides $AB$ and $AD$, respectively, such that $H$ lies inside triangle $SCT$ and $$\angle CHS - \angle CSB = 90°, \quad \angle THC - \angle DTC = 90°.$$

Prove that line $BD$ is tangent to the circumcircle of triangle $TSH$.

Points $P$ and $Q$ lie on side $BC$ of acute-angled triangle $ABC$ so that $\angle PAB = \angle BCA$ and $\angle CAQ = \angle ABC$. Points $M$ and $N$ lie on lines $AP$ and $AQ$, respectively, such that $P$ is the midpoint of $AM$, and $Q$ is the midpoint of $AN$. Prove that lines $BM$ and $CN$ intersect on the circumcircle of triangle $ABC$.

For each positive integer $n$, the Bank of Cape Town issues coins of denomination $\frac{1}{n}$. Given a finite collection of such coins (of not necessarily different denominations) with total value at most $99 + \frac{1}{2}$, prove that it is possible to split this collection into 100 or fewer groups, such that each group has total value at most 1.

A set of lines in the plane is in general position if no two are parallel and no three pass through the same point. A set of lines in general position cuts the plane into regions, some of which have finite area; we call these its finite regions. Prove that for all sufficiently large $n$, in any set of $n$ lines in general position it is possible to colour at least $\sqrt{n}$ of the lines blue in such a way that none of its finite regions has a completely blue boundary.

Note: Results with $\sqrt{n}$ replaced by $c\sqrt{n}$ will be awarded points depending on the value of the constant $c$.

Prove that for any pair of positive integers $k$ and $n$, there exist $k$ positive integers $m_1, m_2, \ldots, m_k$ (not necessarily different) such that

$$1 + \frac{2^k - 1}{n} = \left(1 + \frac{1}{m_1}\right)\left(1 + \frac{1}{m_2}\right) \cdots \left(1 + \frac{1}{m_k}\right).$$

A configuration of 4027 points in the plane is called Colombian if it consists of 2013 red points and 2014 blue points, and no three of the points of the configuration are collinear. By drawing some lines, the plane is divided into several regions. An arrangement of lines is good for a Colombian configuration if the following two conditions are satisfied:

• no line passes through any point of the configuration;
• no region contains points of both colours.

Find the least value of $k$ such that for any Colombian configuration of 4027 points, there is a good arrangement of $k$ lines.

Let the excircle of triangle $ABC$ opposite the vertex $A$ be tangent to the side $BC$ at the point $A_1$. Define the points $B_1$ on $CA$ and $C_1$ on $AB$ analogously, using the excircles opposite $B$ and $C$, respectively. Suppose that the circumcentre of triangle $A_1B_1C_1$ lies on the circumcircle of triangle $ABC$. Prove that triangle $ABC$ is right-angled.

The excircle of triangle $ABC$ opposite the vertex $A$ is the circle that is tangent to the line segment $BC$, to the ray $AB$ beyond $B$, and to the ray $AC$ beyond $C$. The excircles opposite $B$ and $C$ are similarly defined.

Let $ABC$ be an acute-angled triangle with orthocentre $H$, and let $W$ be a point on the side $BC$, lying strictly between $B$ and $C$. The points $M$ and $N$ are the feet of the altitudes from $B$ and $C$, respectively. Denote by $\omega_1$ the circumcircle of $BWN$, and let $X$ be the point on $\omega_1$ such that $WX$ is a diameter of $\omega_1$. Analogously, denote by $\omega_2$ the circumcircle of $CWM$, and let $Y$ be the point on $\omega_2$ such that $WY$ is a diameter of $\omega_2$. Prove that $X$, $Y$ and $H$ are collinear.

Let $\mathbb{Q}_{>0}$ be the set of positive rational numbers. Let $f: \mathbb{Q}_{>0} \to \mathbb{R}$ be a function satisfying the following three conditions:

(i) for all $x, y \in \mathbb{Q}_{>0}$, we have $f(x)f(y) \geq f(xy)$;

(ii) for all $x, y \in \mathbb{Q}_{>0}$, we have $f(x + y) \geq f(x) + f(y)$;

(iii) there exists a rational number $a > 1$ such that $f(a) = a$.

Prove that $f(x) = x$ for all $x \in \mathbb{Q}_{>0}$.

Let $n \geq 3$ be an integer, and consider a circle with $n + 1$ equally spaced points marked on it. Consider all labellings of these points with the numbers $0, 1, \ldots, n$ such that each label is used exactly once; two such labellings are considered to be the same if one can be obtained from the other by a rotation of the circle. A labelling is called beautiful if, for any four labels $a < b < c < d$ with $a + d = b + c$, the chord joining the points labelled $a$ and $d$ does not intersect the chord joining the points labelled $b$ and $c$.

Let $M$ be the number of beautiful labellings, and let $N$ be the number of ordered pairs $(x,y)$ of positive integers such that $x + y \leq n$ and $\gcd(x,y) = 1$. Prove that

$$M = N + 1.$$

Given triangle $ABC$ the point $J$ is the centre of the excircle opposite the vertex $A$. This excircle is tangent to the side $BC$ at $M$, and to the lines $AB$ and $AC$ at $K$ and $L$, respectively. The lines $LM$ and $BJ$ meet at $F$, and the lines $KM$ and $CJ$ meet at $G$. Let $S$ be the point of intersection of the lines $AF$ and $BC$, and let $T$ be the point of intersection of the lines $AG$ and $BC$.

Prove that $M$ is the midpoint of $ST$.

(The excircle of $ABC$ opposite the vertex $A$ is the circle that is tangent to the line segment $BC$, to the ray $AB$ beyond $B$, and to the ray $AC$ beyond $C$.)

Let $n \geq 3$ be an integer, and let $a_2, a_3, \ldots, a_n$ be positive real numbers such that $a_2a_3 \cdots a_n = 1$. Prove that $$(1 + a_2)^2(1 + a_3)^3 \cdots (1 + a_n)^n > n^n.$$

The liar's guessing game is a game played between two players $A$ and $B$. The rules of the game depend on two positive integers $k$ and $n$ which are known to both players.

At the start of the game $A$ chooses integers $x$ and $N$ with $1 \leq x \leq N$. Player $A$ keeps $x$ secret, and truthfully tells $N$ to player $B$. Player $B$ now tries to obtain information about $x$ by asking player $A$ questions as follows: each question consists of $B$ specifying an arbitrary set $S$ of positive integers (possibly one specified in some previous question), and asking $A$ whether $x$ belongs to $S$. Player $B$ may ask as many such questions as he wishes. After each question, player $A$ must immediately answer it with yes or no, but is allowed to lie as many times as she wants; the only restriction is that, among any $k + 1$ consecutive answers, at least one answer must be truthful.

After $B$ has asked as many questions as he wants, he must specify a set $X$ of at most $n$ positive integers. If $x$ belongs to $X$, then $B$ wins; otherwise, he loses. Prove that:

1. If $n \geq 2^k$, then $B$ can guarantee a win.
2. For all sufficiently large $k$, there exists an integer $n \geq 1.99^k$ such that $B$ cannot guarantee a win.

Find all functions $f : \mathbb{Z} \to \mathbb{Z}$ such that, for all integers $a, b, c$ that satisfy $a + b + c = 0$, the following equality holds: $$f(a)^2 + f(b)^2 + f(c)^2 = 2f(a)f(b) + 2f(b)f(c) + 2f(c)f(a).$$

(Here $\mathbb{Z}$ denotes the set of integers.)

Let $ABC$ be a triangle with $\angle BCA = 90°$, and let $D$ be the foot of the altitude from $C$. Let $X$ be a point in the interior of the segment $CD$. Let $K$ be the point on the segment $AX$ such that $BK = BC$. Similarly, let $L$ be the point on the segment $BX$ such that $AL = AC$. Let $M$ be the point of intersection of $AL$ and $BK$.

Show that $MK = ML$.

Find all positive integers $n$ for which there exist non-negative integers $a_1, a_2, \ldots, a_n$ such that $$\frac{1}{2^{a_1}} + \frac{1}{2^{a_2}} + \cdots + \frac{1}{2^{a_n}} = \frac{1}{3^{a_1}} + \frac{2}{3^{a_2}} + \cdots + \frac{n}{3^{a_n}} = 1.$$

Given any set $A = \{a_1, a_2, a_3, a_4\}$ of four distinct positive integers, we denote the sum $a_1 + a_2 + a_3 + a_4$ by $s_A$. Let $n_A$ denote the number of pairs $(i,j)$ with $1 \leq i < j \leq 4$ for which $a_i + a_j$ divides $s_A$. Find all sets $A$ of four distinct positive integers which achieve the largest possible value of $n_A$.

Let $\mathcal{S}$ be a finite set of at least two points in the plane. Assume that no three points of $\mathcal{S}$ are collinear. A windmill is a process that starts with a line $\ell$ going through a single point $P \in \mathcal{S}$. The line rotates clockwise about the pivot $P$ until the first time that the line meets some other point belonging to $\mathcal{S}$. This point, $Q$, takes over as the new pivot, and the line now rotates clockwise about $Q$, until it next meets a point of $\mathcal{S}$. This process continues indefinitely.

Show that we can choose a point $P$ in $\mathcal{S}$ and a line $\ell$ going through $P$ such that the resulting windmill uses each point of $\mathcal{S}$ as a pivot infinitely many times.

Let $f: \mathbb{R} \to \mathbb{R}$ be a real-valued function defined on the set of real numbers that satisfies $$f(x + y) \leq yf(x) + f(f(x))$$ for all real numbers $x$ and $y$. Prove that $f(x) = 0$ for all $x \leq 0$.

Let $n > 0$ be an integer. We are given a balance and $n$ weights of weight $2^0, 2^1, \ldots, 2^{n-1}$. We are to place each of the $n$ weights on the balance, one after another, in such a way that the right pan is never heavier than the left pan. At each step we choose one of the weights that has not yet been placed on the balance, and place it on either the left pan or the right pan, until all of the weights have been placed.

Determine the number of ways in which this can be done.

Let $f$ be a function from the set of integers to the set of positive integers. Suppose that, for any two integers $m$ and $n$, the difference $f(m) - f(n)$ is divisible by $f(m - n)$. Prove that, for all integers $m$ and $n$ with $f(m) \leq f(n)$, the number $f(n)$ is divisible by $f(m)$.

Let $ABC$ be an acute triangle with circumcircle $\Gamma$. Let $\ell$ be a tangent line to $\Gamma$, and let $\ell_a$, $\ell_b$ and $\ell_c$ be the lines obtained by reflecting $\ell$ in the lines $BC$, $CA$ and $AB$, respectively. Show that the circumcircle of the triangle determined by the lines $\ell_a$, $\ell_b$ and $\ell_c$ is tangent to the circle $\Gamma$.

Determine all functions $f\colon \mathbb{R}\to \mathbb{R}$ such that the equality $$f \big (\lfloor x \rfloor y \big) = f (x) \big \lfloor f (y) \rfloor$$ holds for all $x, y \in \mathbb{R}$. (Here $\lfloor z \rfloor$ denotes the greatest integer less than or equal to $z$.)

Let $I$ be the incentre of triangle $ABC$ and let $\Gamma$ be its circumcircle. Let the line $AI$ intersect $\Gamma$ again at $D$. Let $E$ be a point on the arc $\widehat{BDC}$ and $F$ a point on the side $BC$ such that $$\angle BAF = \angle CAE < \frac{1}{2}\angle BAC.$$ Finally, let $G$ be the midpoint of the segment $IF$. Prove that the lines $DG$ and $EI$ intersect on $\Gamma$.

Let $\mathbb{N}$ be the set of positive integers. Determine all functions $g\colon \mathbb{N}\to \mathbb{N}$ such that $$\left(g (m) + n\right) \left(m + g (n)\right)$$ is a perfect square for all $m, n \in \mathbb{N}$.

Let $P$ be a point inside the triangle $ABC$. The lines $AP$, $BP$ and $CP$ intersect the circumcircle $\Gamma$ of triangle $ABC$ again at the points $K$, $L$ and $M$ respectively. The tangent to $\Gamma$ at $C$ intersects the line $AB$ at $S$. Suppose that $SC = SP$. Prove that $MK = ML$.

In each of six boxes $B_{1}, B_{2}, B_{3}, B_{4}, B_{5}, B_{6}$ there is initially one coin. There are two types of operation allowed:

Type 1: Choose a nonempty box $B_{j}$ with $1 \leq j \leq 5$. Remove one coin from $B_{j}$ and add two coins to $B_{j+1}$.

Type 2: Choose a nonempty box $B_{k}$ with $1 \leq k \leq 4$. Remove one coin from $B_{k}$ and exchange the contents of (possibly empty) boxes $B_{k+1}$ and $B_{k+2}$.

Determine whether there is a finite sequence of such operations that results in boxes $B_{1}, B_{2}, B_{3}, B_{4}, B_{5}$ being empty and box $B_{6}$ containing exactly $2010^{2010^{2010}}$ coins. (Note that $a^{b^{c}} = a^{(b^{c})}$.)

Let $a_1, a_2, a_3, \ldots$ be a sequence of positive real numbers. Suppose that for some positive integer $s$, we have $$a _ {n} = \max \left\{a _ {k} + a _ {n - k} \mid 1 \leq k \leq n - 1 \right\}$$ for all $n > s$. Prove that there exist positive integers $\ell$ and $N$, with $\ell \leq s$ and such that $a_{n} = a_{\ell} + a_{n - \ell}$ for all $n \geq N$.

Let $n$ be a positive integer and let $a_1, \ldots, a_k$ ($k \geq 2$) be distinct integers in the set $\{1, \ldots, n\}$ such that $n$ divides $a_i(a_{i+1} - 1)$ for $i = 1, \ldots, k-1$. Prove that $n$ does not divide $a_k(a_1 - 1)$.

Let $ABC$ be a triangle with circumcentre $O$. The points $P$ and $Q$ are interior points of the sides $CA$ and $AB$, respectively. Let $K$, $L$ and $M$ be the midpoints of the segments $BP$, $CQ$ and $PQ$, respectively, and let $\Gamma$ be the circle passing through $K$, $L$ and $M$. Suppose that the line $PQ$ is tangent to the circle $\Gamma$. Prove that $OP = OQ$.

Suppose that $s_1, s_2, s_3, \ldots$ is a strictly increasing sequence of positive integers such that the subsequences

$$s_{s_1}, s_{s_2}, s_{s_3}, \ldots \quad \text{and} \quad s_{s_1 + 1}, s_{s_2 + 1}, s_{s_3 + 1}, \ldots$$

are both arithmetic progressions. Prove that the sequence $s_1, s_2, s_3, \ldots$ is itself an arithmetic progression.

Let $ABC$ be a triangle with $AB = AC$. The angle bisectors of $\angle CAB$ and $\angle ABC$ meet the sides $BC$ and $CA$ at $D$ and $E$, respectively. Let $K$ be the incentre of triangle $ADC$. Suppose that $\angle BEK = 45^{\circ}$. Find all possible values of $\angle CAB$.