International Mathematical Olympiad

A line in the plane is called sunny if it is not parallel to any of the $x$-axis, the $y$-axis, and the line $x + y = 0$.

Let $n \geqslant 3$ be a given integer. Determine all nonnegative integers $k$ such that there exist $n$ distinct lines in the plane satisfying both of the following:

• for all positive integers $a$ and $b$ with $a + b \leqslant n + 1$, the point $(a, b)$ is on at least one of the lines; and
• exactly $k$ of the $n$ lines are sunny.

Let $\Omega$ and $\Gamma$ be circles with centres $M$ and $N$, respectively, such that the radius of $\Omega$ is less than the radius of $\Gamma$. Suppose circles $\Omega$ and $\Gamma$ intersect at two distinct points $A$ and $B$. Line $MN$ intersects $\Omega$ at $C$ and $\Gamma$ at $D$, such that points $C$, $M$, $N$ and $D$ lie on the line in that order. Let $P$ be the circumcentre of triangle $ACD$. Line $AP$ intersects $\Omega$ again at $E \neq A$. Line $AP$ intersects $\Gamma$ again at $F \neq A$. Let $H$ be the orthocentre of triangle $PMN$.

Prove that the line through $H$ parallel to $AP$ is tangent to the circumcircle of triangle $BEF$.

(The orthocentre of a triangle is the point of intersection of its altitudes.)

Let $\mathbb{N}$ denote the set of positive integers. A function $f\colon \mathbb{N}\to \mathbb{N}$ is said to be bonza if

$$f(a) \; \text{ divides } \; b^a - f(b)^{f(a)}$$

for all positive integers $a$ and $b$.

Determine the smallest real constant $c$ such that $f(n) \leqslant cn$ for all bonza functions $f$ and all positive integers $n$.

A proper divisor of a positive integer $N$ is a positive divisor of $N$ other than $N$ itself.

The infinite sequence $a_1, a_2, \ldots$ consists of positive integers, each of which has at least three proper divisors. For each $n \geqslant 1$, the integer $a_{n+1}$ is the sum of the three largest proper divisors of $a_n$.

Determine all possible values of $a_1$.

Alice and Bazza are playing the inekoalaty game, a two-player game whose rules depend on a positive real number $\lambda$ which is known to both players. On the $n^{\text{th}}$ turn of the game (starting with $n = 1$) the following happens:

• If $n$ is odd, Alice chooses a nonnegative real number $x_n$ such that

$$x_1 + x_2 + \cdots + x_n \leqslant \lambda n.$$

• If $n$ is even, Bazza chooses a nonnegative real number $x_n$ such that

$$x_1^2 + x_2^2 + \cdots + x_n^2 \leqslant n.$$

If a player cannot choose a suitable number $x_n$, the game ends and the other player wins. If the game goes on forever, neither player wins. All chosen numbers are known to both players.

Determine all values of $\lambda$ for which Alice has a winning strategy and all those for which Bazza has a winning strategy.

Consider a $2025 \times 2025$ grid of unit squares. Matilda wishes to place on the grid some rectangular tiles, possibly of different sizes, such that each side of every tile lies on a grid line and every unit square is covered by at most one tile.

Determine the minimum number of tiles Matilda needs to place so that each row and each column of the grid has exactly one unit square that is not covered by any tile.

Determine all real numbers $\alpha$ such that, for every positive integer $n$, the integer $$\lfloor \alpha \rfloor + \lfloor 2\alpha \rfloor + \cdots + \lfloor n\alpha \rfloor$$ is a multiple of $n$. (Note that $\lfloor z \rfloor$ denotes the greatest integer less than or equal to $z$. For example, $\lfloor -\pi \rfloor = -4$ and $\lfloor 2 \rfloor = \lfloor 2.9 \rfloor = 2$.)

Determine all pairs $(a, b)$ of positive integers for which there exist positive integers $g$ and $N$ such that $$\gcd(a^n + b, b^n + a) = g$$ holds for all integers $n \geq N$. (Note that $\gcd(x, y)$ denotes the greatest common divisor of integers $x$ and $y$.)

Let $a_1, a_2, a_3, \ldots$ be an infinite sequence of positive integers, and let $N$ be a positive integer. Suppose that, for each $n > N$, $a_n$ is equal to the number of times $a_{n-1}$ appears in the list $a_1, a_2, \ldots, a_{n-1}$.

Prove that at least one of the sequences $a_1, a_3, a_5, \ldots$ and $a_2, a_4, a_6, \ldots$ is eventually periodic.

(An infinite sequence $b_1, b_2, b_3, \ldots$ is eventually periodic if there exist positive integers $p$ and $M$ such that $b_{m+p} = b_m$ for all $m \geq M$.)

Let $ABC$ be a triangle with $AB < AC < BC$. Let the incentre and incircle of triangle $ABC$ be $I$ and $\omega$, respectively. Let $X$ be the point on line $BC$ different from $C$ such that the line through $X$ parallel to $AC$ is tangent to $\omega$. Similarly, let $Y$ be the point on line $BC$ different from $B$ such that the line through $Y$ parallel to $AB$ is tangent to $\omega$. Let $AI$ intersect the circumcircle of triangle $ABC$ again at $P \neq A$. Let $K$ and $L$ be the midpoints of $AC$ and $AB$, respectively.

Prove that $\angle KIL + \angle YPX = 180^{\circ}$.

Turbo the snail plays a game on a board with 2024 rows and 2023 columns. There are hidden monsters in 2022 of the cells. Initially, Turbo does not know where any of the monsters are, but he knows that there is exactly one monster in each row except the first row and the last row, and that each column contains at most one monster.

Turbo makes a series of attempts to go from the first row to the last row. On each attempt, he chooses to start on any cell in the first row, then repeatedly moves to an adjacent cell sharing a common side. (He is allowed to return to a previously visited cell.) If he reaches a cell with a monster, his attempt ends and he is transported back to the first row to start a new attempt. The monsters do not move, and Turbo remembers whether or not each cell he has visited contains a monster. If he reaches any cell in the last row, his attempt ends and the game is over.

Determine the minimum value of $n$ for which Turbo has a strategy that guarantees reaching the last row on the $n^{\text{th}}$ attempt or earlier, regardless of the locations of the monsters.

Let $\mathbb{Q}$ be the set of rational numbers. A function $f\colon \mathbb{Q} \to \mathbb{Q}$ is called aquaesulian if the following property holds: for every $x, y \in \mathbb{Q}$, $$f(x + f(y)) = f(x) + y \quad \text{or} \quad f(f(x) + y) = x + f(y).$$

Show that there exists an integer $c$ such that for any aquaesulian function $f$ there are at most $c$ different rational numbers of the form $f(r) + f(-r)$ for some rational number $r$, and find the smallest possible value of $c$.

Determine all composite integers $n > 1$ that satisfy the following property: if $d_1, d_2, \ldots, d_k$ are all the positive divisors of $n$ with $1 = d_1 < d_2 < \cdots < d_k = n$, then $d_i$ divides $d_{i+1} + d_{i+2}$ for every $1 \leqslant i \leqslant k-2$.

Let $ABC$ be an acute-angled triangle with $AB < AC$. Let $\Omega$ be the circumcircle of $ABC$. Let $S$ be the midpoint of the arc $CB$ of $\Omega$ containing $A$. The perpendicular from $A$ to $BC$ meets $BS$ at $D$ and meets $\Omega$ again at $E \neq A$. The line through $D$ parallel to $BC$ meets line $BE$ at $L$. Denote the circumcircle of triangle $BDL$ by $\omega$. Let $\omega$ meet $\Omega$ again at $P \neq B$. Prove that the line tangent to $\omega$ at $P$ meets line $BS$ on the internal angle bisector of $\measuredangle BAC$.

For each integer $k \geqslant 2$, determine all infinite sequences of positive integers $a_1, a_2, \ldots$ for which there exists a polynomial $P$ of the form $P(x) = x^k + c_{k-1}x^{k-1} + \cdots + c_1x + c_0$, where $c_0, c_1, \ldots, c_{k-1}$ are non-negative integers, such that

$$P(a_n) = a_{n+1}a_{n+2}\cdots a_{n+k}$$

for every integer $n \geqslant 1$.

Let $x_1, x_2, \ldots, x_{2023}$ be pairwise different positive real numbers such that

$$a_n = \sqrt{(x_1 + x_2 + \cdots + x_n)\left(\frac{1}{x_1} + \frac{1}{x_2} + \cdots + \frac{1}{x_n}\right)}$$

is an integer for every $n = 1, 2, \ldots, 2023$. Prove that $a_{2023} \geqslant 3034$.

Let $n$ be a positive integer. A Japanese triangle consists of $1 + 2 + \cdots + n$ circles arranged in an equilateral triangular shape such that for each $i = 1, 2, \ldots, n$, the $i^{\text{th}}$ row contains exactly $i$ circles, exactly one of which is coloured red. A ninja path in a Japanese triangle is a sequence of $n$ circles obtained by starting in the top row, then repeatedly going from a circle to one of the two circles immediately below it and finishing in the bottom row. Here is an example of a Japanese triangle with $n = 6$, along with a ninja path in that triangle containing two red circles.

In terms of $n$, find the greatest $k$ such that in each Japanese triangle there is a ninja path containing at least $k$ red circles.

Let $ABC$ be an equilateral triangle. Let $A_1, B_1, C_1$ be interior points of $ABC$ such that $BA_1 = A_1C$, $CB_1 = B_1A$, $AC_1 = C_1B$, and

$$\angle BA_1C + \angle CB_1A + \angle AC_1B = 480°.$$

Let $BC_1$ and $CB_1$ meet at $A_2$, let $CA_1$ and $AC_1$ meet at $B_2$, and let $AB_1$ and $BA_1$ meet at $C_2$. Prove that if triangle $A_1B_1C_1$ is scalene, then the three circumcircles of triangles $AA_1A_2$, $BB_1B_2$ and $CC_1C_2$ all pass through two common points.

(Note: a scalene triangle is one where no two sides have equal length.)

The Bank of Oslo issues two types of coin: aluminium (denoted $A$) and bronze (denoted $B$). Marianne has $n$ aluminium coins and $n$ bronze coins, arranged in a row in some arbitrary initial order. A chain is any subsequence of consecutive coins of the same type. Given a fixed positive integer $k \leq 2n$, Marianne repeatedly performs the following operation: she identifies the longest chain containing the $k^{\text{th}}$ coin from the left, and moves all coins in that chain to the left end of the row. For example, if $n = 4$ and $k = 4$, the process starting from the ordering $AABBBABA$ would be

$$AAB\underline{B}BABA \rightarrow BBB\underline{A}AABA \rightarrow AAA\underline{B}BBBA \rightarrow BBB\underline{B}AAAA \rightarrow BBB\underline{B}AAAA \rightarrow \cdots.$$

Find all pairs $(n,k)$ with $1 \leq k \leq 2n$ such that for every initial ordering, at some moment during the process, the leftmost $n$ coins will all be of the same type.

Let $\mathbb{R}^+$ denote the set of positive real numbers. Find all functions $f: \mathbb{R}^+ \to \mathbb{R}^+$ such that for each $x \in \mathbb{R}^+$, there is exactly one $y \in \mathbb{R}^+$ satisfying

$$xf(y) + yf(x) \leq 2.$$

Let $k$ be a positive integer and let $S$ be a finite set of odd prime numbers. Prove that there is at most one way (up to rotation and reflection) to place the elements of $S$ around a circle such that the product of any two neighbours is of the form $x^2 + x + k$ for some positive integer $x$.

Let $ABCDE$ be a convex pentagon such that $BC = DE$. Assume that there is a point $T$ inside $ABCDE$ with $TB = TD$, $TC = TE$ and $\angle ABT = \angle TEA$. Let line $AB$ intersect lines $CD$ and $CT$ at points $P$ and $Q$, respectively. Assume that the points $P, B, A, Q$ occur on their line in that order. Let line $AE$ intersect lines $CD$ and $DT$ at points $R$ and $S$, respectively. Assume that the points $R, E, A, S$ occur on their line in that order. Prove that the points $P, S, Q, R$ lie on a circle.

Find all triples $(a, b, p)$ of positive integers with $p$ prime and

$$a^p = b! + p.$$

Let $n$ be a positive integer. A Nordic square is an $n \times n$ board containing all the integers from 1 to $n^2$ so that each cell contains exactly one number. Two different cells are considered adjacent if they share a common side. Every cell that is adjacent only to cells containing larger numbers is called a valley. An uphill path is a sequence of one or more cells such that:

(i) the first cell in the sequence is a valley,

(ii) each subsequent cell in the sequence is adjacent to the previous cell, and

(iii) the numbers written in the cells in the sequence are in increasing order.

Find, as a function of $n$, the smallest possible total number of uphill paths in a Nordic square.

Let $n \geqslant 100$ be an integer. Ivan writes the numbers $n, n + 1, \ldots, 2n$ each on different cards. He then shuffles these $n + 1$ cards, and divides them into two piles. Prove that at least one of the piles contains two cards such that the sum of their numbers is a perfect square.

Show that the inequality $$\sum_{i=1}^{n} \sum_{j=1}^{n} \sqrt{|x_i - x_j|} \leqslant \sum_{i=1}^{n} \sum_{j=1}^{n} \sqrt{|x_i + x_j|}$$ holds for all real numbers $x_1, \ldots, x_n$.

Let $D$ be an interior point of the acute triangle $ABC$ with $AB > AC$ so that $\angle DAB = \angle CAD$. The point $E$ on the segment $AC$ satisfies $\angle ADE = \angle BCD$, the point $F$ on the segment $AB$ satisfies $\angle FDA = \angle DBC$, and the point $X$ on the line $AC$ satisfies $CX = BX$. Let $O_1$ and $O_2$ be the circumcentres of the triangles $ADC$ and $EXD$, respectively. Prove that the lines $BC$, $EF$, and $O_1O_2$ are concurrent.

Let $\Gamma$ be a circle with centre $I$, and $ABCD$ a convex quadrilateral such that each of the segments $AB$, $BC$, $CD$ and $DA$ is tangent to $\Gamma$. Let $\Omega$ be the circumcircle of the triangle $AIC$. The extension of $BA$ beyond $A$ meets $\Omega$ at $X$, and the extension of $BC$ beyond $C$ meets $\Omega$ at $Z$. The extensions of $AD$ and $CD$ beyond $D$ meet $\Omega$ at $Y$ and $T$, respectively. Prove that $$AD + DT + TX + XA = CD + DY + YZ + ZC.$$

Two squirrels, Bushy and Jumpy, have collected 2021 walnuts for the winter. Jumpy numbers the walnuts from 1 through 2021, and digs 2021 little holes in a circular pattern in the ground around their favourite tree. The next morning Jumpy notices that Bushy had placed one walnut into each hole, but had paid no attention to the numbering. Unhappy, Jumpy decides to reorder the walnuts by performing a sequence of 2021 moves. In the $k$-th move, Jumpy swaps the positions of the two walnuts adjacent to walnut $k$.

Prove that there exists a value of $k$ such that, on the $k$-th move, Jumpy swaps some walnuts $a$ and $b$ such that $a < k < b$.

Let $m \geqslant 2$ be an integer, $A$ be a finite set of (not necessarily positive) integers, and $B_1, B_2, B_3, \ldots, B_m$ be subsets of $A$. Assume that for each $k = 1, 2, \ldots, m$ the sum of the elements of $B_k$ is $m^k$. Prove that $A$ contains at least $m/2$ elements.

Consider the convex quadrilateral $ABCD$. The point $P$ is in the interior of $ABCD$. The following ratio equalities hold: $$\angle PAD : \angle PBA : \angle DPA = 1 : 2 : 3 = \angle CBP : \angle BAP : \angle BPC.$$

Prove that the following three lines meet in a point: the internal bisectors of angles $\angle ADP$ and $\angle PCB$ and the perpendicular bisector of segment $AB$.

The real numbers $a, b, c, d$ are such that $a \geq b \geq c \geq d > 0$ and $a + b + c + d = 1$. Prove that $$(a + 2b + 3c + 4d) a^a b^b c^c d^d < 1.$$

There are $4n$ pebbles of weights $1, 2, 3, \ldots, 4n$. Each pebble is coloured in one of $n$ colours and there are four pebbles of each colour. Show that we can arrange the pebbles into two piles so that the following two conditions are both satisfied:

• The total weights of both piles are the same.
• Each pile contains two pebbles of each colour.

There is an integer $n > 1$. There are $n^2$ stations on a slope of a mountain, all at different altitudes. Each of two cable car companies, $A$ and $B$, operates $k$ cable cars; each cable car provides a transfer from one of the stations to a higher one (with no intermediate stops). The $k$ cable cars of $A$ have $k$ different starting points and $k$ different finishing points, and a cable car which starts higher also finishes higher. The same conditions hold for $B$. We say that two stations are linked by a company if one can start from the lower station and reach the higher one by using one or more cars of that company (no other movements between stations are allowed).

Determine the smallest positive integer $k$ for which one can guarantee that there are two stations that are linked by both companies.

A deck of $n > 1$ cards is given. A positive integer is written on each card. The deck has the property that the arithmetic mean of the numbers on each pair of cards is also the geometric mean of the numbers on some collection of one or more cards.

For which $n$ does it follow that the numbers on the cards are all equal?

Prove that there exists a positive constant $c$ such that the following statement is true:

Consider an integer $n > 1$, and a set $S$ of $n$ points in the plane such that the distance between any two different points in $S$ is at least 1. It follows that there is a line $\ell$ separating $S$ such that the distance from any point of $S$ to $\ell$ is at least $cn^{-1/3}$.

(A line $\ell$ separates a set of points $S$ if some segment joining two points in $S$ crosses $\ell$.)

Note. Weaker results with $cn^{-1/3}$ replaced by $cn^{-\alpha}$ may be awarded points depending on the value of the constant $\alpha > 1/3$.

Let $\mathbb{Z}$ be the set of integers. Determine all functions $f: \mathbb{Z} \to \mathbb{Z}$ such that, for all integers $a$ and $b$, $$f(2a) + 2f(b) = f(f(a + b)).$$

In triangle $ABC$, point $A_1$ lies on side $BC$ and point $B_1$ lies on side $AC$. Let $P$ and $Q$ be points on segments $AA_1$ and $BB_1$, respectively, such that $PQ$ is parallel to $AB$. Let $P_1$ be a point on line $PB_1$, such that $B_1$ lies strictly between $P$ and $P_1$, and $\angle PP_1C = \angle BAC$. Similarly, let $Q_1$ be a point on line $QA_1$, such that $A_1$ lies strictly between $Q$ and $Q_1$, and $\angle CQ_1Q = \angle CBA$.

Prove that points $P$, $Q$, $P_1$, and $Q_1$ are concyclic.

A social network has 2019 users, some pairs of whom are friends. Whenever user $A$ is friends with user $B$, user $B$ is also friends with user $A$. Events of the following kind may happen repeatedly, one at a time:

Three users $A$, $B$, and $C$ such that $A$ is friends with both $B$ and $C$, but $B$ and $C$ are not friends, change their friendship statuses such that $B$ and $C$ are now friends, but $A$ is no longer friends with $B$, and no longer friends with $C$. All other friendship statuses are unchanged.

Initially, 1010 users have 1009 friends each, and 1009 users have 1010 friends each. Prove that there exists a sequence of such events after which each user is friends with at most one other user.

Find all pairs $(k, n)$ of positive integers such that $$k! = (2^n - 1)(2^n - 2)(2^n - 4) \cdots (2^n - 2^{n-1}).$$

The Bank of Bath issues coins with an $H$ on one side and a $T$ on the other. Harry has $n$ of these coins arranged in a line from left to right. He repeatedly performs the following operation: if there are exactly $k > 0$ coins showing $H$, then he turns over the $k$th coin from the left; otherwise, all coins show $T$ and he stops. For example, if $n = 3$ the process starting with the configuration $THT$ would be $THT \to HHT \to HTT \to TTT$, which stops after three operations.

(a) Show that, for each initial configuration, Harry stops after a finite number of operations.

(b) For each initial configuration $C$, let $L(C)$ be the number of operations before Harry stops. For example, $L(THT) = 3$ and $L(TTT) = 0$. Determine the average value of $L(C)$ over all $2^n$ possible initial configurations $C$.

Let $I$ be the incentre of acute triangle $ABC$ with $AB \neq AC$. The incircle $\omega$ of $ABC$ is tangent to sides $BC$, $CA$, and $AB$ at $D$, $E$, and $F$, respectively. The line through $D$ perpendicular to $EF$ meets $\omega$ again at $R$. Line $AR$ meets $\omega$ again at $P$. The circumcircles of triangles $PCE$ and $PBF$ meet again at $Q$.

Prove that lines $DI$ and $PQ$ meet on the line through $A$ perpendicular to $AI$.

Let $\Gamma$ be the circumcircle of acute-angled triangle $ABC$. Points $D$ and $E$ lie on segments $AB$ and $AC$, respectively, such that $AD = AE$. The perpendicular bisectors of $BD$ and $CE$ intersect the minor arcs $AB$ and $AC$ of $\Gamma$ at points $F$ and $G$, respectively. Prove that the lines $DE$ and $FG$ are parallel (or are the same line).

Find all integers $n \geq 3$ for which there exist real numbers $a_1, a_2, \ldots, a_{n+2}$, such that $a_{n+1} = a_1$ and $a_{n+2} = a_2$, and $$a_i a_{i+1} + 1 = a_{i+2}$$ for $i = 1, 2, \ldots, n$.

An anti-Pascal triangle is an equilateral triangular array of numbers such that, except for the numbers in the bottom row, each number is the absolute value of the difference of the two numbers immediately below it. For example, the following array is an anti-Pascal triangle with four rows which contains every integer from 1 to 10.

$$\begin{array}{ccccccc} & & & 4 & & & \\ & & 2 & & 6 & & \\ & 5 & & 7 & & 1 & \\ 8 & & 3 & & 10 & & 9 \end{array}$$

Does there exist an anti-Pascal triangle with 2018 rows which contains every integer from 1 to $1 + 2 + \cdots + 2018$?

A site is any point $(x, y)$ in the plane such that $x$ and $y$ are both positive integers less than or equal to 20.

Initially, each of the 400 sites is unoccupied. Amy and Ben take turns placing stones with Amy going first. On her turn, Amy places a new red stone on an unoccupied site such that the distance between any two sites occupied by red stones is not equal to $\sqrt{5}$. On his turn, Ben places a new blue stone on any unoccupied site. (A site occupied by a blue stone is allowed to be at any distance from any other occupied site.) They stop as soon as a player cannot place a stone.

Find the greatest $K$ such that Amy can ensure that she places at least $K$ red stones, no matter how Ben places his blue stones.

Let $a_1, a_2, \ldots$ be an infinite sequence of positive integers. Suppose that there is an integer $N > 1$ such that, for each $n \geq N$, the number $$\frac{a_1}{a_2} + \frac{a_2}{a_3} + \cdots + \frac{a_{n-1}}{a_n} + \frac{a_n}{a_1}$$ is an integer. Prove that there is a positive integer $M$ such that $a_m = a_{m+1}$ for all $m \geq M$.

A convex quadrilateral $ABCD$ satisfies $AB \cdot CD = BC \cdot DA$. Point $X$ lies inside $ABCD$ so that $$\angle XAB = \angle XCD \quad \text{and} \quad \angle XBC = \angle XDA.$$ Prove that $\angle BXA + \angle DXC = 180°$.

For each integer $a_0 > 1$, define the sequence $a_0, a_1, a_2, \ldots$ by:

$$a_{n+1} = \begin{cases} \sqrt{a_n} & \text{if } \sqrt{a_n} \text{ is an integer,} \\ a_n + 3 & \text{otherwise,} \end{cases} \quad \text{for each } n \geqslant 0.$$

Determine all values of $a_0$ for which there is a number $A$ such that $a_n = A$ for infinitely many values of $n$.

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