IMO 2021 — Complete Shortlist

Let $n$ be an integer, and let $A$ be a subset of $\left\{0,1,2,3, \ldots, 5^{n}\right\}$ consisting of $4 n+2$ numbers. Prove that there exist $a, b, c \in A$ such that $a\lt b\lt c$ and $c+2 a\gt 3 b$.

For every integer $n \geqslant 1$ consider the $n \times n$ table with entry $\left\lfloor\frac{i j}{n+1}\right\rfloor$ at the intersection of row $i$ and column $j$, for every $i=1, \ldots, n$ and $j=1, \ldots, n$. Determine all integers $n \geqslant 1$ for which the sum of the $n^{2}$ entries in the table is equal to $\frac{1}{4} n^{2}(n-1)$.

Given a positive integer $n$, find the smallest value of $\left\lfloor\frac{a_{1}}{1}\right\rfloor+\left\lfloor\frac{a_{2}}{2}\right\rfloor+\cdots+\left\lfloor\frac{a_{n}}{n}\right\rfloor$ over all permutations $\left(a_{1}, a_{2}, \ldots, a_{n}\right)$ of $(1,2, \ldots, n)$.

Show that for all real numbers $x_{1}, \ldots, x_{n}$ the following inequality holds:

$$
\sum_{i=1}^{n} \sum_{j=1}^{n} \sqrt{\left|x_{i}-x_{j}\right|} \leqslant \sum_{i=1}^{n} \sum_{j=1}^{n} \sqrt{\left|x_{i}+x_{j}\right|}
$$

Let $n \geqslant 2$ be an integer, and let $a_{1}, a_{2}, \ldots, a_{n}$ be positive real numbers such that $a_{1}+a_{2}+\cdots+a_{n}=1$. Prove that

$$
\sum_{k=1}^{n} \frac{a_{k}}{1-a_{k}}\left(a_{1}+a_{2}+\cdots+a_{k-1}\right)^{2}\lt \frac{1}{3}
$$

Let $A$ be a finite set of (not necessarily positive) integers, and let $m \geqslant 2$ be an integer. Assume that there exist non-empty subsets $B_{1}, B_{2}, B_{3}, \ldots, B_{m}$ of $A$ whose elements add up to the sums $m^{1}, m^{2}, m^{3}, \ldots, m^{m}$, respectively. Prove that $A$ contains at least $m / 2$ elements.

Let $n \geqslant 1$ be an integer, and let $x_{0}, x_{1}, \ldots, x_{n+1}$ be $n+2$ non-negative real numbers that satisfy $x_{i} x_{i+1}-x_{i-1}^{2} \geqslant 1$ for all $i=1,2, \ldots, n$. Show that

$$
x_{0}+x_{1}+\cdots+x_{n}+x_{n+1}\gt \left(\frac{2 n}{3}\right)^{3 / 2}
$$

Determine all functions $f: \mathbb{R} \rightarrow \mathbb{R}$ that satisfy

$$
(f(a)-f(b))(f(b)-f(c))(f(c)-f(a))=f\left(a b^{2}+b c^{2}+c a^{2}\right)-f\left(a^{2} b+b^{2} c+c^{2} a\right)
$$

for all real numbers $a, b, c$.

Let $S$ be an infinite set of positive integers, such that there exist four pairwise distinct $a, b, c, d \in S$ with $\operatorname{gcd}(a, b) \neq \operatorname{gcd}(c, d)$. Prove that there exist three pairwise distinct $x, y, z \in S$ such that $\operatorname{gcd}(x, y)=\operatorname{gcd}(y, z) \neq \operatorname{gcd}(z, x)$.

Let $n \geqslant 3$ be an integer. An integer $m \geqslant n+1$ is called $n$-colourful if, given infinitely many marbles in each of $n$ colours $C_{1}, C_{2}, \ldots, C_{n}$, it is possible to place $m$ of them around a circle so that in any group of $n+1$ consecutive marbles there is at least one marble of colour $C_{i}$ for each $i=1, \ldots, n$.

Prove that there are only finitely many positive integers which are not $n$-colourful. Find the largest among them.

A thimblerigger has 2021 thimbles numbered from 1 through 2021. The thimbles are arranged in a circle in arbitrary order. The thimblerigger performs a sequence of 2021 moves; in the $k^{\text {th }}$ move, he swaps the positions of the two thimbles adjacent to thimble $k$.

Prove that there exists a value of $k$ such that, in the $k^{\text {th }}$ move, the thimblerigger swaps some thimbles $a$ and $b$ such that $a\lt k\lt b$.

The kingdom of Anisotropy consists of $n$ cities. For every two cities there exists exactly one direct one-way road between them. We say that a path from $X$ to $Y$ is a sequence of roads such that one can move from $X$ to $Y$ along this sequence without returning to an already visited city. A collection of paths is called diverse if no road belongs to two or more paths in the collection.

Let $A$ and $B$ be two distinct cities in Anisotropy. Let $N_{A B}$ denote the maximal number of paths in a diverse collection of paths from $A$ to $B$. Similarly, let $N_{B A}$ denote the maximal number of paths in a diverse collection of paths from $B$ to $A$. Prove that the equality $N_{A B}=N_{B A}$ holds if and only if the number of roads going out from $A$ is the same as the number of roads going out from $B$.

Let $n$ and $k$ be two integers with $n\gt k \geqslant 1$. There are $2 n+1$ students standing in a circle. Each student $S$ has $2 k$ neighbours - namely, the $k$ students closest to $S$ on the right, and the $k$ students closest to $S$ on the left.

Suppose that $n+1$ of the students are girls, and the other $n$ are boys. Prove that there is a girl with at least $k$ girls among her neighbours.

A hunter and an invisible rabbit play a game on an infinite square grid. First the hunter fixes a colouring of the cells with finitely many colours. The rabbit then secretly chooses a cell to start in. Every minute, the rabbit reports the colour of its current cell to the hunter, and then secretly moves to an adjacent cell that it has not visited before (two cells are adjacent if they share a side). The hunter wins if after some finite time either

- the rabbit cannot move; or
- the hunter can determine the cell in which the rabbit started.

Decide whether there exists a winning strategy for the hunter.

Consider a checkered $3 m \times 3 m$ square, where $m$ is an integer greater than 1. A frog sits on the lower left corner cell $S$ and wants to get to the upper right corner cell $F$. The frog can hop from any cell to either the next cell to the right or the next cell upwards.

Some cells can be sticky, and the frog gets trapped once it hops on such a cell. A set $X$ of cells is called blocking if the frog cannot reach $F$ from $S$ when all the cells of $X$ are sticky. A blocking set is minimal if it does not contain a smaller blocking set.
(a) Prove that there exists a minimal blocking set containing at least $3 m^{2}-3 m$ cells.
(b) Prove that every minimal blocking set contains at most $3 m^{2}$ cells.

Note. An example of a minimal blocking set for $m=2$ is shown below. Cells of the set $X$ are marked by letters $x$.

| | | | | | $F$ |
| :--- | :--- | :--- | :--- | :--- | :--- |
| $x$ | $x$ | | | | |
| | | $x$ | | | |
| | | | $x$ | | |
| | | | | $x$ | |
| $S$ | | $x$ | | | |

Original illustration of the example:

Determine the largest $N$ for which there exists a table $T$ of integers with $N$ rows and 100 columns that has the following properties:
(i) Every row contains the numbers $1,2, \ldots, 100$ in some order.
(ii) For any two distinct rows $r$ and $s$, there is a column $c$ such that $|T(r, c)-T(s, c)| \geqslant 2$.

Here $T(r, c)$ means the number at the intersection of the row $r$ and the column $c$.

Let $A B C D$ be a parallelogram such that $A C=B C$. A point $P$ is chosen on the extension of the segment $A B$ beyond $B$. The circumcircle of the triangle $A C D$ meets the segment $P D$ again at $Q$, and the circumcircle of the triangle $A P Q$ meets the segment $P C$ again at $R$. Prove that the lines $C D, A Q$, and $B R$ are concurrent.

Let $A B C D$ be a convex quadrilateral circumscribed around a circle with centre $I$. Let $\omega$ be the circumcircle of the triangle $A C I$. The extensions of $B A$ and $B C$ beyond $A$ and $C$ meet $\omega$ at $X$ and $Z$, respectively. The extensions of $A D$ and $C D$ beyond $D$ meet $\omega$ at $Y$ and $T$, respectively. Prove that the perimeters of the (possibly self-intersecting) quadrilaterals $A D T X$ and $C D Y Z$ are equal.

Version 1. Let $n$ be a fixed positive integer, and let S be the set of points $(x, y)$ on the Cartesian plane such that both coordinates $x$ and $y$ are nonnegative integers smaller than $2 n$ (thus $|\mathrm{S}|=4 n^{2}$ ). Assume that $\mathcal{F}$ is a set consisting of $n^{2}$ quadrilaterals such that all their vertices lie in $S$, and each point in $S$ is a vertex of exactly one of the quadrilaterals in $\mathcal{F}$.

Determine the largest possible sum of areas of all $n^{2}$ quadrilaterals in $\mathcal{F}$.
Version 2. Let $n$ be a fixed positive integer, and let $\mathbf{S}$ be the set of points $(x, y)$ on the Cartesian plane such that both coordinates $x$ and $y$ are nonnegative integers smaller than $2 n$ (thus $|\mathrm{S}|=4 n^{2}$ ). Assume that $\mathcal{F}$ is a set of polygons such that all vertices of polygons in $\mathcal{F}$ lie in S , and each point in S is a vertex of exactly one of the polygons in $\mathcal{F}$.

Let $A B C D$ be a quadrilateral inscribed in a circle $\Omega$. Let the tangent to $\Omega$ at $D$ intersect the rays $B A$ and $B C$ at points $E$ and $F$, respectively. A point $T$ is chosen inside the triangle $A B C$ so that $T E \| C D$ and $T F \| A D$. Let $K \neq D$ be a point on the segment $D F$ such that $T D=T K$. Prove that the lines $A C, D T$ and $B K$ intersect at one point.