IMO 2018 — Complete Shortlist

Let $\mathbb{Q}_{\gt 0}$ denote the set of all positive rational numbers. Determine all functions $f: \mathbb{Q}_{\gt 0} \rightarrow \mathbb{Q}_{\gt 0}$ satisfying

$$
f\left(x^{2} f(y)^{2}\right)=f(x)^{2} f(y)
$$

for all $x, y \in \mathbb{Q}_{\gt 0}$.

Find all positive integers $n \geqslant 3$ for which there exist real numbers $a_{1}, a_{2}, \ldots, a_{n}$, $a_{n+1}=a_{1}, a_{n+2}=a_{2}$ such that

$$
a_{i} a_{i+1}+1=a_{i+2}
$$

for all $i=1,2, \ldots, n$.

Given any set $S$ of positive integers, show that at least one of the following two assertions holds:

(1) There exist distinct finite subsets $F$ and $G$ of $S$ such that $\sum_{x \in F} 1 / x=\sum_{x \in G} 1 / x$;

(2) There exists a positive rational number $r\lt 1$ such that $\sum_{x \in F} 1 / x \neq r$ for all finite subsets $F$ of $S$.

Let $a_{0}, a_{1}, a_{2}, \ldots$ be a sequence of real numbers such that $a_{0}=0, a_{1}=1$, and for every $n \geqslant 2$ there exists $1 \leqslant k \leqslant n$ satisfying

$$
a_{n}=\frac{a_{n-1}+\cdots+a_{n-k}}{k}
$$

Find the maximal possible value of $a_{2018}-a_{2017}$.

Determine all functions $f:(0, \infty) \rightarrow \mathbb{R}$ satisfying

$$
\left(x+\frac{1}{x}\right) f(y)=f(x y)+f\left(\frac{y}{x}\right)
$$

for all $x, y\gt 0$.

Let $m, n \geqslant 2$ be integers. Let $f\left(x_{1}, \ldots, x_{n}\right)$ be a polynomial with real coefficients such that

$$
f\left(x_{1}, \ldots, x_{n}\right)=\left\lfloor\frac{x_{1}+\ldots+x_{n}}{m}\right\rfloor \text { for every } x_{1}, \ldots, x_{n} \in\{0,1, \ldots, m-1\}
$$

Prove that the total degree of $f$ is at least $n$.

Find the maximal value of

$$
S=\sqrt[3]{\frac{a}{b+7}}+\sqrt[3]{\frac{b}{c+7}}+\sqrt[3]{\frac{c}{d+7}}+\sqrt[3]{\frac{d}{a+7}}
$$

where $a, b, c, d$ are nonnegative real numbers which satisfy $a+b+c+d=100$.

Let $n \geqslant 3$ be an integer. Prove that there exists a set $S$ of $2 n$ positive integers satisfying the following property: For every $m=2,3, \ldots, n$ the set $S$ can be partitioned into two subsets with equal sums of elements, with one of subsets of cardinality $m$.

Queenie and Horst play a game on a $20 \times 20$ chessboard. In the beginning the board is empty. In every turn, Horst places a black knight on an empty square in such a way that his new knight does not attack any previous knights. Then Queenie places a white queen on an empty square. The game gets finished when somebody cannot move.

Find the maximal positive $K$ such that, regardless of the strategy of Queenie, Horst can put at least $K$ knights on the board.

Let $n$ be a given positive integer. Sisyphus performs a sequence of turns on a board consisting of $n+1$ squares in a row, numbered 0 to $n$ from left to right. Initially, $n$ stones are put into square 0, and the other squares are empty. At every turn, Sisyphus chooses any nonempty square, say with $k$ stones, takes one of those stones and moves it to the right by at most $k$ squares (the stone should stay within the board). Sisyphus' aim is to move all $n$ stones to square $n$.

Prove that Sisyphus cannot reach the aim in less than

$$
\left\lceil\frac{n}{1}\right\rceil+\left\lceil\frac{n}{2}\right\rceil+\left\lceil\frac{n}{3}\right\rceil+\cdots+\left\lceil\frac{n}{n}\right\rceil
$$

turns. (As usual, $\lceil x\rceil$ stands for the least integer not smaller than $x$.)

An anti-Pascal pyramid is a finite set of numbers, placed in a triangle-shaped array so that the first row of the array contains one number, the second row contains two numbers, the third row contains three numbers and so on; and, except for the numbers in the bottom row, each number equals the absolute value of the difference of the two numbers below it. For instance, the triangle below is an anti-Pascal pyramid with four rows, in which every integer from 1 to $1+2+3+4=10$ occurs exactly once:

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

Is it possible to form an anti-Pascal pyramid with 2018 rows, using every integer from 1 to $1+2+\cdots+2018$ exactly once?

Source illustration of the example above:

Let $k$ be a positive integer. The organising committee of a tennis tournament is to schedule the matches for $2 k$ players so that every two players play once, each day exactly one match is played, and each player arrives to the tournament site the day of his first match, and departs the day of his last match. For every day a player is present on the tournament, the committee has to pay 1 coin to the hotel. The organisers want to design the schedule so as to minimise the total cost of all players' stays. Determine this minimum cost.

Let $a$ and $b$ be distinct positive integers. The following infinite process takes place on an initially empty board.

(i) If there is at least a pair of equal numbers on the board, we choose such a pair and increase one of its components by $a$ and the other by $b$.

(ii) If no such pair exists, we write down two times the number 0 .

Prove that, no matter how we make the choices in $(i)$, operation (ii) will be performed only finitely many times.

Consider 2018 pairwise crossing circles no three of which are concurrent. These circles subdivide the plane into regions bounded by circular edges that meet at vertices. Notice that there are an even number of vertices on each circle. Given the circle, alternately colour the vertices on that circle red and blue. In doing so for each circle, every vertex is coloured twice once for each of the two circles that cross at that point. If the two colourings agree at a vertex, then it is assigned that colour; otherwise, it becomes yellow. Show that, if some circle contains at least 2061 yellow points, then the vertices of some region are all yellow.

Let $A B C$ be an acute-angled triangle with circumcircle $\Gamma$. Let $D$ and $E$ be points on the segments $A B$ and $A C$, respectively, such that $A D=A E$. The perpendicular bisectors of the segments $B D$ and $C E$ intersect the small arcs $\overset{\frown}{A B}$ and $\overset{\frown}{A C}$ at points $F$ and $G$ respectively. Prove that $D E \| F G$.

Let $A B C$ be a triangle with $A B=A C$, and let $M$ be the midpoint of $B C$. Let $P$ be a point such that $P B\lt P C$ and $P A$ is parallel to $B C$. Let $X$ and $Y$ be points on the lines $P B$ and $P C$, respectively, so that $B$ lies on the segment $P X, C$ lies on the segment $P Y$, and $\angle P X M=\angle P Y M$. Prove that the quadrilateral $A P X Y$ is cyclic.

A circle $\omega$ of radius 1 is given. A collection $T$ of triangles is called good, if the following conditions hold:

(i) each triangle from $T$ is inscribed in $\omega$;

(ii) no two triangles from $T$ have a common interior point.

Determine all positive real numbers $t$ such that, for each positive integer $n$, there exists a good collection of $n$ triangles, each of perimeter greater than $t$.

A point $T$ is chosen inside a triangle $A B C$. Let $A_{1}, B_{1}$, and $C_{1}$ be the reflections of $T$ in $B C, C A$, and $A B$, respectively. Let $\Omega$ be the circumcircle of the triangle $A_{1} B_{1} C_{1}$. The lines $A_{1} T, B_{1} T$, and $C_{1} T$ meet $\Omega$ again at $A_{2}, B_{2}$, and $C_{2}$, respectively. Prove that the lines $A A_{2}, B B_{2}$, and $C C_{2}$ are concurrent on $\Omega$.

Let $A B C$ be a triangle with circumcircle $\omega$ and incentre $I$. A line $\ell$ intersects the lines $A I, B I$, and $C I$ at points $D, E$, and $F$, respectively, distinct from the points $A, B, C$, and $I$. The perpendicular bisectors $x, y$, and $z$ of the segments $A D, B E$, and $C F$, respectively determine a triangle $\Theta$. Show that the circumcircle of the triangle $\Theta$ is tangent to $\omega$.

A convex quadrilateral $A B C D$ satisfies $A B \cdot C D=B C \cdot D A$. A point $X$ is chosen inside the quadrilateral so that $\angle X A B=\angle X C D$ and $\angle X B C=\angle X D A$. Prove that $\angle A X B+$ $\angle C X D=180^{\circ}$.