ISL 2020

Version 1. Let $n$ be a positive integer, and set $N=2^{n}$. Determine the smallest real number $a_{n}$ such that, for all real $x$, $$\sqrt[N]{\frac{x^{2 N}+1}{2}} \leqslant a_{n}(x-1)^{2}+x$$ Version 2. For every positive integer $N$, determine the smallest real number $b_{N}$ such that, for all real $x$, $$\sqrt[N]{\frac{x^{2 N}+1}{2}} \leqslant b_{N}(x-1)^{2}+x$$ (Ireland)

Let $\mathcal{A}$ denote the set of all polynomials in three variables $x, y, z$ with integer coefficients. Let $\mathcal{B}$ denote the subset of $\mathcal{A}$ formed by all polynomials which can be expressed as $$(x+y+z) P(x, y, z)+(x y+y z+z x) Q(x, y, z)+x y z R(x, y, z)$$ with $P, Q, R \in \mathcal{A}$. Find the smallest non-negative integer $n$ such that $x^{i} y^{j} z^{k} \in \mathcal{B}$ for all nonnegative integers $i, j, k$ satisfying $i+j+k \geqslant n$. (Venezuela)

Suppose that $a, b, c, d$ are positive real numbers satisfying $(a+c)(b+d)=a c+b d$. Find the smallest possible value of $$\frac{a}{b}+\frac{b}{c}+\frac{c}{d}+\frac{d}{a}$$

Let $a, b, c, d$ be four real numbers such that $a \geqslant b \geqslant c \geqslant d>0$ and $a+b+c+d=1$. Prove that $$(a+2 b+3 c+4 d) a^{a} b^{b} c^{c} d^{d}<1$$ (Belgium)

A magician intends to perform the following trick. She announces a positive integer $n$, along with $2 n$ real numbers $x_{1}<\ldots<x_{2 n}$, to the audience. A member of the audience then secretly chooses a polynomial $P(x)$ of degree $n$ with real coefficients, computes the $2 n$ values $P\left(x_{1}\right), \ldots, P\left(x_{2 n}\right)$, and writes down these $2 n$ values on the blackboard in non-decreasing order. After that the magician announces the secret polynomial to the audience. Can the magician find a strategy to perform such a trick? (Luxembourg)

Determine all functions $f: \mathbb{Z} \rightarrow \mathbb{Z}$ such that $$f^{a^{2}+b^{2}}(a+b)=a f(a)+b f(b) \text { for every } a, b \in \mathbb{Z}$$ Here, $f^{n}$ denotes the $n^{\text {th }}$ iteration of $f$, i.e., $f^{0}(x)=x$ and $f^{n+1}(x)=f\left(f^{n}(x)\right)$ for all $n \geqslant 0$.

Let $n$ and $k$ be positive integers. Prove that for $a_{1}, \ldots, a_{n} \in\left[1,2^{k}\right]$ one has $$\sum_{i=1}^{n} \frac{a_{i}}{\sqrt{a_{1}^{2}+\ldots+a_{i}^{2}}} \leqslant 4 \sqrt{k n}$$ (Iran)

Let $\mathbb{R}^{+}$be the set of positive real numbers. Determine all functions $f: \mathbb{R}^{+} \rightarrow \mathbb{R}^{+}$ such that, for all positive real numbers $x$ and $y$, $$f(x+f(x y))+y=f(x) f(y)+1$$ (Ukraine)

Let $n$ be a positive integer. Find the number of permutations $a_{1}, a_{2}, \ldots, a_{n}$ of the sequence $1,2, \ldots, n$ satisfying $$a_{1} \leqslant 2 a_{2} \leqslant 3 a_{3} \leqslant \ldots \leqslant n a_{n}$$ (United Kingdom)

In a regular 100-gon, 41 vertices are colored black and the remaining 59 vertices are colored white. Prove that there exist 24 convex quadrilaterals $Q_{1}, \ldots, Q_{24}$ whose corners are vertices of the 100 -gon, so that - the quadrilaterals $Q_{1}, \ldots, Q_{24}$ are pairwise disjoint, and - every quadrilateral $Q_{i}$ has three corners of one color and one corner of the other color. (Austria)

Let $n$ be an integer with $n \geqslant 2$. On a slope of a mountain, $n^{2}$ checkpoints are marked, numbered from 1 to $n^{2}$ from the bottom to the top. Each of two cable car companies, $A$ and $B$, operates $k$ cable cars numbered from 1 to $k$; each cable car provides a transfer from some checkpoint to a higher one. For each company, and for any $i$ and $j$ with $1 \leqslant i<j \leqslant k$, the starting point of car $j$ is higher than the starting point of car $i$; similarly, the finishing point of car $j$ is higher than the finishing point of car $i$. Say that two checkpoints are linked by some company if one can start from the lower checkpoint and reach the higher one by using one or more cars of that company (no movement on foot is allowed). Determine the smallest $k$ for which one can guarantee that there are two checkpoints that are linked by each of the two companies. (India)

The Fibonacci numbers $F_{0}, F_{1}, F_{2}, \ldots$ are defined inductively by $F_{0}=0, F_{1}=1$, and $F_{n+1}=F_{n}+F_{n-1}$ for $n \geqslant 1$. Given an integer $n \geqslant 2$, determine the smallest size of a set $S$ of integers such that for every $k=2,3, \ldots, n$ there exist some $x, y \in S$ such that $x-y=F_{k}$. (Croatia)

Let $p$ be an odd prime, and put $N=\frac{1}{4}\left(p^{3}-p\right)-1$. The numbers $1,2, \ldots, N$ are painted arbitrarily in two colors, red and blue. For any positive integer $n \leqslant N$, denote by $r(n)$ the fraction of integers in $\{1,2, \ldots, n\}$ that are red. Prove that there exists a positive integer $a \in\{1,2, \ldots, p-1\}$ such that $r(n) \neq a / p$ for all $n=1,2, \ldots, N$. (Netherlands)

$4 n$ coins of weights $1,2,3, \ldots, 4 n$ are given. Each coin is colored in one of $n$ colors and there are four coins of each color. Show that all these coins can be partitioned into two sets with the same total weight, such that each set contains two coins of each color. (Hungary)

Consider any rectangular table having finitely many rows and columns, with a real number $a(r, c)$ in the cell in row $r$ and column $c$. A pair $(R, C)$, where $R$ is a set of rows and $C$ a set of columns, is called a saddle pair if the following two conditions are satisfied: (i) For each row $r^{\prime}$, there is $r \in R$ such that $a(r, c) \geqslant a\left(r^{\prime}, c\right)$ for all $c \in C$; (ii) For each column $c^{\prime}$, there is $c \in C$ such that $a(r, c) \leqslant a\left(r, c^{\prime}\right)$ for all $r \in R$. A saddle pair $(R, C)$ is called a minimal pair if for each saddle pair ( $R^{\prime}, C^{\prime}$ ) with $R^{\prime} \subseteq R$ and $C^{\prime} \subseteq C$, we have $R^{\prime}=R$ and $C^{\prime}=C$. Prove that any two minimal pairs contain the same number of rows. (Thailand)

Players $A$ and $B$ play a game on a blackboard that initially contains 2020 copies of the number 1. In every round, player $A$ erases two numbers $x$ and $y$ from the blackboard, and then player $B$ writes one of the numbers $x+y$ and $|x-y|$ on the blackboard. The game terminates as soon as, at the end of some round, one of the following holds: (1) one of the numbers on the blackboard is larger than the sum of all other numbers; (2) there are only zeros on the blackboard. Player $B$ must then give as many cookies to player $A$ as there are numbers on the blackboard. Player $A$ wants to get as many cookies as possible, whereas player $B$ wants to give as few as possible. Determine the number of cookies that $A$ receives if both players play optimally.

Let $A B C$ be an isosceles triangle with $B C=C A$, and let $D$ be a point inside side $A B$ such that $A D<D B$. Let $P$ and $Q$ be two points inside sides $B C$ and $C A$, respectively, such that $\angle D P B=\angle D Q A=90^{\circ}$. Let the perpendicular bisector of $P Q$ meet line segment $C Q$ at $E$, and let the circumcircles of triangles $A B C$ and $C P Q$ meet again at point $F$, different from $C$. Suppose that $P, E, F$ are collinear. Prove that $\angle A C B=90^{\circ}$. (Luxembourg)

Let $A B C D$ be a convex quadrilateral. Suppose that $P$ is a point in the interior of $A B C D$ such that $$\angle P A D: \angle P B A: \angle D P A=1: 2: 3=\angle C B P: \angle B A P: \angle B P C .$$ The internal bisectors of angles $A D P$ and $P C B$ meet at a point $Q$ inside the triangle $A B P$. Prove that $A Q=B Q$. (Poland)

Let $A B C D$ be a convex quadrilateral with $\angle A B C>90^{\circ}, \angle C D A>90^{\circ}$, and $\angle D A B=\angle B C D$. Denote by $E$ and $F$ the reflections of $A$ in lines $B C$ and $C D$, respectively. Suppose that the segments $A E$ and $A F$ meet the line $B D$ at $K$ and $L$, respectively. Prove that the circumcircles of triangles $B E K$ and $D F L$ are tangent to each other. (Slovakia)

In the plane, there are $n \geqslant 6$ pairwise disjoint disks $D_{1}, D_{2}, \ldots, D_{n}$ with radii $R_{1} \geqslant R_{2} \geqslant \ldots \geqslant R_{n}$. For every $i=1,2, \ldots, n$, a point $P_{i}$ is chosen in disk $D_{i}$. Let $O$ be an arbitrary point in the plane. Prove that $$O P_{1}+O P_{2}+\ldots+O P_{n} \geqslant R_{6}+R_{7}+\ldots+R_{n}$$ (A disk is assumed to contain its boundary.) (Iran)

Let $A B C D$ be a cyclic quadrilateral with no two sides parallel. Let $K, L, M$, and $N$ be points lying on sides $A B, B C, C D$, and $D A$, respectively, such that $K L M N$ is a rhombus with $K L \| A C$ and $L M \| B D$. Let $\omega_{1}, \omega_{2}, \omega_{3}$, and $\omega_{4}$ be the incircles of triangles $A N K$, $B K L, C L M$, and $D M N$, respectively. Prove that the internal common tangents to $\omega_{1}$ and $\omega_{3}$ and the internal common tangents to $\omega_{2}$ and $\omega_{4}$ are concurrent. (Poland)

Let $I$ and $I_{A}$ be the incenter and the $A$-excenter of an acute-angled triangle $A B C$ with $A B<A C$. Let the incircle meet $B C$ at $D$. The line $A D$ meets $B I_{A}$ and $C I_{A}$ at $E$ and $F$, respectively. Prove that the circumcircles of triangles $A I D$ and $I_{A} E F$ are tangent to each other. (Slovakia)

Let $P$ be a point on the circumcircle of an acute-angled triangle $A B C$. Let $D$, $E$, and $F$ be the reflections of $P$ in the midlines of triangle $A B C$ parallel to $B C, C A$, and $A B$, respectively. Denote by $\omega_{A}, \omega_{B}$, and $\omega_{C}$ the circumcircles of triangles $A D P, B E P$, and $C F P$, respectively. Denote by $\omega$ the circumcircle of the triangle formed by the perpendicular bisectors of segments $A D, B E$ and $C F$. Show that $\omega_{A}, \omega_{B}, \omega_{C}$, and $\omega$ have a common point. (Denmark)

Let $\Gamma$ and $I$ be the circumcircle and the incenter of an acute-angled triangle $A B C$. Two circles $\omega_{B}$ and $\omega_{C}$ passing through $B$ and $C$, respectively, are tangent at $I$. Let $\omega_{B}$ meet the shorter arc $A B$ of $\Gamma$ and segment $A B$ again at $P$ and $M$, respectively. Similarly, let $\omega_{C}$ meet the shorter arc $A C$ of $\Gamma$ and segment $A C$ again at $Q$ and $N$, respectively. The rays $P M$ and $Q N$ meet at $X$, and the tangents to $\omega_{B}$ and $\omega_{C}$ at $B$ and $C$, respectively, meet at $Y$. Prove that the points $A, X$, and $Y$ are collinear. (Netherlands)

Prove that there exists a positive constant $c$ such that the following statement is true: Assume that $n$ is an integer with $n \geqslant 2$, and let $\mathcal{S}$ be a set of $n$ points in the plane such that the distance between any two distinct points in $\mathcal{S}$ is at least 1 . Then there is a line $\ell$ separating $\mathcal{S}$ such that the distance from any point of $\mathcal{S}$ to $\ell$ is at least $c n^{-1 / 3}$. (A line $\ell$ separates a point set $\mathcal{S}$ if some segment joining two points in $\mathcal{S}$ crosses $\ell$.)

Given a positive integer $k$, show that there exists a prime $p$ such that one can choose distinct integers $a_{1}, a_{2}, \ldots, a_{k+3} \in\{1,2, \ldots, p-1\}$ such that $p$ divides $a_{i} a_{i+1} a_{i+2} a_{i+3}-i$ for all $i=1,2, \ldots, k$. (South Africa)

For each prime $p$, there is a kingdom of $p$-Landia consisting of $p$ islands numbered $1,2, \ldots, p$. Two distinct islands numbered $n$ and $m$ are connected by a bridge if and only if $p$ divides $\left(n^{2}-m+1\right)\left(m^{2}-n+1\right)$. The bridges may pass over each other, but cannot cross. Prove that for infinitely many $p$ there are two islands in $p$-Landia not connected by a chain of bridges. (Denmark)

Let $n$ be an integer with $n \geqslant 2$. Does there exist a sequence $\left(a_{1}, \ldots, a_{n}\right)$ of positive integers with not all terms being equal such that the arithmetic mean of every two terms is equal to the geometric mean of some (one or more) terms in this sequence? (Estonia)

For any odd prime $p$ and any integer $n$, let $d_{p}(n) \in\{0,1, \ldots, p-1\}$ denote the remainder when $n$ is divided by $p$. We say that $\left(a_{0}, a_{1}, a_{2}, \ldots\right)$ is a $p$-sequence, if $a_{0}$ is a positive integer coprime to $p$, and $a_{n+1}=a_{n}+d_{p}\left(a_{n}\right)$ for $n \geqslant 0$. (a) Do there exist infinitely many primes $p$ for which there exist $p$-sequences $\left(a_{0}, a_{1}, a_{2}, \ldots\right)$ and $\left(b_{0}, b_{1}, b_{2}, \ldots\right)$ such that $a_{n}>b_{n}$ for infinitely many $n$, and $b_{n}>a_{n}$ for infinitely many $n$ ? (b) Do there exist infinitely many primes $p$ for which there exist $p$-sequences $\left(a_{0}, a_{1}, a_{2}, \ldots\right)$ and $\left(b_{0}, b_{1}, b_{2}, \ldots\right)$ such that $a_{0}<b_{0}$, but $a_{n}>b_{n}$ for all $n \geqslant 1$ ? (United Kingdom)

Determine all functions $f$ defined on the set of all positive integers and taking non-negative integer values, satisfying the three conditions: (i) $f(n) \neq 0$ for at least one $n$; (ii) $f(x y)=f(x)+f(y)$ for every positive integers $x$ and $y$; (iii) there are infinitely many positive integers $n$ such that $f(k)=f(n-k)$ for all $k<n$. (Croatia)

For a positive integer $n$, let $d(n)$ be the number of positive divisors of $n$, and let $\varphi(n)$ be the number of positive integers not exceeding $n$ which are coprime to $n$. Does there exist a constant $C$ such that $$\frac{\varphi(d(n))}{d(\varphi(n))} \leqslant C$$ for all $n \geqslant 1$ ? (Cyprus)

Let $\mathcal{S}$ be a set consisting of $n \geqslant 3$ positive integers, none of which is a sum of two other distinct members of $\mathcal{S}$. Prove that the elements of $\mathcal{S}$ may be ordered as $a_{1}, a_{2}, \ldots, a_{n}$ so that $a_{i}$ does not divide $a_{i-1}+a_{i+1}$ for all $i=2,3, \ldots, n-1$. (Ukraine)