ISL 2021

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<b<c$ and $c+2 a>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}<\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}>\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<k<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>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$.

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 $|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 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}$. Determine the largest possible sum of areas of all 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.

Let $A B C D$ be a cyclic quadrilateral whose sides have pairwise different lengths. Let $O$ be the circumcentre of $A B C D$. The internal angle bisectors of $\angle A B C$ and $\angle A D C$ meet $A C$ at $B_{1}$ and $D_{1}$, respectively. Let $O_{B}$ be the centre of the circle which passes through $B$ and is tangent to $A C$ at $D_{1}$. Similarly, let $O_{D}$ be the centre of the circle which passes through $D$ and is tangent to $A C$ at $B_{1}$. Assume that $B D_{1} \| D B_{1}$. Prove that $O$ lies on the line $O_{B} O_{D}$.

Determine all integers $n \geqslant 3$ satisfying the following property: every convex $n$-gon whose sides all have length 1 contains an equilateral triangle of side length 1. (Every polygon is assumed to contain its boundary.)

A point $D$ is chosen inside an acute-angled triangle $A B C$ with $A B>A C$ so that $\angle B A D=\angle D A C$. A point $E$ is constructed on the segment $A C$ so that $\angle A D E=\angle D C B$. Similarly, a point $F$ is constructed on the segment $A B$ so that $\angle A D F=\angle D B C$. A point $X$ is chosen on the line $A C$ so that $C X=B X$. Let $O_{1}$ and $O_{2}$ be the circumcentres of the triangles $A D C$ and $D X E$. Prove that the lines $B C, E F$, and $O_{1} O_{2}$ are concurrent.

Let $\omega$ be the circumcircle of a triangle $A B C$, and let $\Omega_{A}$ be its excircle which is tangent to the segment $B C$. Let $X$ and $Y$ be the intersection points of $\omega$ and $\Omega_{A}$. Let $P$ and $Q$ be the projections of $A$ onto the tangent lines to $\Omega_{A}$ at $X$ and $Y$, respectively. The tangent line at $P$ to the circumcircle of the triangle $A P X$ intersects the tangent line at $Q$ to the circumcircle of the triangle $A Q Y$ at a point $R$. Prove that $A R \perp B C$.

Determine all integers $n \geqslant 1$ for which there exists a pair of positive integers $(a, b)$ such that no cube of a prime divides $a^{2}+b+3$ and $$\frac{a b+3 b+8}{a^{2}+b+3}=n$$

Let $n \geqslant 100$ be an integer. The numbers $n, n+1, \ldots, 2 n$ are written on $n+1$ cards, one number per card. The cards are shuffled and divided into two piles. Prove that one of the piles contains two cards such that the sum of their numbers is a perfect square.

Find all positive integers $n$ with the following property: the $k$ positive divisors of $n$ have a permutation $\left(d_{1}, d_{2}, \ldots, d_{k}\right)$ such that for every $i=1,2, \ldots, k$, the number $d_{1}+\cdots+d_{i}$ is a perfect square.

Alice is given a rational number $r>1$ and a line with two points $B \neq R$, where point $R$ contains a red bead and point $B$ contains a blue bead. Alice plays a solitaire game by performing a sequence of moves. In every move, she chooses a (not necessarily positive) integer $k$, and a bead to move. If that bead is placed at point $X$, and the other bead is placed at $Y$, then Alice moves the chosen bead to point $X^{\prime}$ with $\overrightarrow{Y X^{\prime}}=r^{k} \overrightarrow{Y X}$. Alice's goal is to move the red bead to the point $B$. Find all rational numbers $r>1$ such that Alice can reach her goal in at most 2021 moves.

Prove that there are only finitely many quadruples $(a, b, c, n)$ of positive integers such that $$n!=a^{n-1}+b^{n-1}+c^{n-1} .$$

Determine all integers $n \geqslant 2$ with the following property: every $n$ pairwise distinct integers whose sum is not divisible by $n$ can be arranged in some order $a_{1}, a_{2}, \ldots, a_{n}$ so that $n$ divides $1 \cdot a_{1}+2 \cdot a_{2}+\cdots+n \cdot a_{n}$.

Let $a_{1}, a_{2}, a_{3}, \ldots$ be an infinite sequence of positive integers such that $a_{n+2 m}$ divides $a_{n}+a_{n+m}$ for all positive integers $n$ and $m$. Prove that this sequence is eventually periodic, i.e. there exist positive integers $N$ and $d$ such that $a_{n}=a_{n+d}$ for all $n>N$.

For a polynomial $P(x)$ with integer coefficients let $P^{1}(x)=P(x)$ and $P^{k+1}(x)=$ $P\left(P^{k}(x)\right)$ for $k \geqslant 1$. Find all positive integers $n$ for which there exists a polynomial $P(x)$ with integer coefficients such that for every integer $m \geqslant 1$, the numbers $P^{m}(1), \ldots, P^{m}(n)$ leave exactly $\left\lceil n / 2^{m}\right\rceil$ distinct remainders when divided by $n$.