ISL 2016

Let $a, b$ and $c$ be positive real numbers such that $\min \{a b, b c, c a\} \geqslant 1$. Prove that $$\sqrt[3]{\left(a^{2}+1\right)\left(b^{2}+1\right)\left(c^{2}+1\right)} \leqslant\left(\frac{a+b+c}{3}\right)^{2}+1$$

Find the smallest real constant $C$ such that for any positive real numbers $a_{1}, a_{2}, a_{3}, a_{4}$ and $a_{5}$ (not necessarily distinct), one can always choose distinct subscripts $i, j, k$ and $l$ such that $$\left|\frac{a_{i}}{a_{j}}-\frac{a_{k}}{a_{l}}\right| \leqslant C$$

Find all integers $n \geqslant 3$ with the following property: for all real numbers $a_{1}, a_{2}, \ldots, a_{n}$ and $b_{1}, b_{2}, \ldots, b_{n}$ satisfying $\left|a_{k}\right|+\left|b_{k}\right|=1$ for $1 \leqslant k \leqslant n$, there exist $x_{1}, x_{2}, \ldots, x_{n}$, each of which is either -1 or 1 , such that $$\left|\sum_{k=1}^{n} x_{k} a_{k}\right|+\left|\sum_{k=1}^{n} x_{k} b_{k}\right| \leqslant 1$$

Denote by $\mathbb{R}^{+}$the set of all positive real numbers. Find all functions $f: \mathbb{R}^{+} \rightarrow \mathbb{R}^{+}$such that $$x f\left(x^{2}\right) f(f(y))+f(y f(x))=f(x y)\left(f\left(f\left(x^{2}\right)\right)+f\left(f\left(y^{2}\right)\right)\right)$$ for all positive real numbers $x$ and $y$.

(a) Prove that for every positive integer $n$, there exists a fraction $\frac{a}{b}$ where $a$ and $b$ are integers satisfying $0<b \leqslant \sqrt{n}+1$ and $\sqrt{n} \leqslant \frac{a}{b} \leqslant \sqrt{n+1}$. (b) Prove that there are infinitely many positive integers $n$ such that there is no fraction $\frac{a}{b}$ where $a$ and $b$ are integers satisfying $0<b \leqslant \sqrt{n}$ and $\sqrt{n} \leqslant \frac{a}{b} \leqslant \sqrt{n+1}$.

The equation $$(x-1)(x-2) \cdots(x-2016)=(x-1)(x-2) \cdots(x-2016)$$ is written on the board. One tries to erase some linear factors from both sides so that each side still has at least one factor, and the resulting equation has no real roots. Find the least number of linear factors one needs to erase to achieve this.

Denote by $\mathbb{R}$ the set of all real numbers. Find all functions $f: \mathbb{R} \rightarrow \mathbb{R}$ such that $f(0) \neq 0$ and $$f(x+y)^{2}=2 f(x) f(y)+\max \left\{f\left(x^{2}\right)+f\left(y^{2}\right), f\left(x^{2}+y^{2}\right)\right\}$$ for all real numbers $x$ and $y$.

Determine the largest real number $a$ such that for all $n \geqslant 1$ and for all real numbers $x_{0}, x_{1}, \ldots, x_{n}$ satisfying $0=x_{0}<x_{1}<x_{2}<\cdots<x_{n}$, we have $$\frac{1}{x_{1}-x_{0}}+\frac{1}{x_{2}-x_{1}}+\cdots+\frac{1}{x_{n}-x_{n-1}} \geqslant a\left(\frac{2}{x_{1}}+\frac{3}{x_{2}}+\cdots+\frac{n+1}{x_{n}}\right) .$$

The leader of an IMO team chooses positive integers $n$ and $k$ with $n>k$, and announces them to the deputy leader and a contestant. The leader then secretly tells the deputy leader an $n$-digit binary string, and the deputy leader writes down all $n$-digit binary strings which differ from the leader's in exactly $k$ positions. (For example, if $n=3$ and $k=1$, and if the leader chooses 101, the deputy leader would write down 001, 111 and 100.) The contestant is allowed to look at the strings written by the deputy leader and guess the leader's string. What is the minimum number of guesses (in terms of $n$ and $k$ ) needed to guarantee the correct answer?

Find all positive integers $n$ for which all positive divisors of $n$ can be put into the cells of a rectangular table under the following constraints: - each cell contains a distinct divisor; - the sums of all rows are equal; and - the sums of all columns are equal.

Let $n$ be a positive integer relatively prime to 6 . We paint the vertices of a regular $n$-gon with three colours so that there is an odd number of vertices of each colour. Show that there exists an isosceles triangle whose three vertices are of different colours. $\mathbf{C 4}$. Find all positive integers $n$ for which we can fill in the entries of an $n \times n$ table with the following properties: - each entry can be one of $I, M$ and $O$; - in each row and each column, the letters $I, M$ and $O$ occur the same number of times; and - in any diagonal whose number of entries is a multiple of three, the letters $I, M$ and $O$ occur the same number of times.

Find all positive integers $n$ for which we can fill in the entries of an $n \times n$ table with the following properties: - each entry can be one of $I, M$ and $O$; - in each row and each column, the letters $I, M$ and $O$ occur the same number of times; and - in any diagonal whose number of entries is a multiple of three, the letters $I, M$ and $O$ occur the same number of times.

Let $n \geqslant 3$ be a positive integer. Find the maximum number of diagonals of a regular $n$-gon one can select, so that any two of them do not intersect in the interior or they are perpendicular to each other.

There are $n \geqslant 3$ islands in a city. Initially, the ferry company offers some routes between some pairs of islands so that it is impossible to divide the islands into two groups such that no two islands in different groups are connected by a ferry route. After each year, the ferry company will close a ferry route between some two islands $X$ and $Y$. At the same time, in order to maintain its service, the company will open new routes according to the following rule: for any island which is connected by a ferry route to exactly one of $X$ and $Y$, a new route between this island and the other of $X$ and $Y$ is added. Suppose at any moment, if we partition all islands into two nonempty groups in any way, then it is known that the ferry company will close a certain route connecting two islands from the two groups after some years. Prove that after some years there will be an island which is connected to all other islands by ferry routes.

Let $n \geqslant 2$ be an integer. In the plane, there are $n$ segments given in such a way that any two segments have an intersection point in the interior, and no three segments intersect at a single point. Jeff places a snail at one of the endpoints of each of the segments and claps his hands $n-1$ times. Each time when he claps his hands, all the snails move along their own segments and stay at the next intersection points until the next clap. Since there are $n-1$ intersection points on each segment, all snails will reach the furthest intersection points from their starting points after $n-1$ claps. (a) Prove that if $n$ is odd then Jeff can always place the snails so that no two of them ever occupy the same intersection point. (b) Prove that if $n$ is even then there must be a moment when some two snails occupy the same intersection point no matter how Jeff places the snails.

Let $n$ be a positive integer. Determine the smallest positive integer $k$ with the following property: it is possible to mark $k$ cells on a $2 n \times 2 n$ board so that there exists a unique partition of the board into $1 \times 2$ and $2 \times 1$ dominoes, none of which contains two marked cells.

In a convex pentagon $A B C D E$, let $F$ be a point on $A C$ such that $\angle F B C=90^{\circ}$. Suppose triangles $A B F, A C D$ and $A D E$ are similar isosceles triangles with $$\angle F A B=\angle F B A=\angle D A C=\angle D C A=\angle E A D=\angle E D A$$ Let $M$ be the midpoint of $C F$. Point $X$ is chosen such that $A M X E$ is a parallelogram. Show that $B D, E M$ and $F X$ are concurrent.

Let $A B C$ be a triangle with circumcircle $\Gamma$ and incentre $I$. Let $M$ be the midpoint of side $B C$. Denote by $D$ the foot of perpendicular from $I$ to side $B C$. The line through $I$ perpendicular to $A I$ meets sides $A B$ and $A C$ at $F$ and $E$ respectively. Suppose the circumcircle of triangle $A E F$ intersects $\Gamma$ at a point $X$ other than $A$. Prove that lines $X D$ and $A M$ meet on $\Gamma$.

Let $B=(-1,0)$ and $C=(1,0)$ be fixed points on the coordinate plane. A nonempty, bounded subset $S$ of the plane is said to be nice if (i) there is a point $T$ in $S$ such that for every point $Q$ in $S$, the segment $T Q$ lies entirely in $S$; and (ii) for any triangle $P_{1} P_{2} P_{3}$, there exists a unique point $A$ in $S$ and a permutation $\sigma$ of the indices $\{1,2,3\}$ for which triangles $A B C$ and $P_{\sigma(1)} P_{\sigma(2)} P_{\sigma(3)}$ are similar. Prove that there exist two distinct nice subsets $S$ and $S^{\prime}$ of the set $\{(x, y): x \geqslant 0, y \geqslant 0\}$ such that if $A \in S$ and $A^{\prime} \in S^{\prime}$ are the unique choices of points in (ii), then the product $B A \cdot B A^{\prime}$ is a constant independent of the triangle $P_{1} P_{2} P_{3}$.

Let $A B C$ be a triangle with $A B=A C \neq B C$ and let $I$ be its incentre. The line $B I$ meets $A C$ at $D$, and the line through $D$ perpendicular to $A C$ meets $A I$ at $E$. Prove that the reflection of $I$ in $A C$ lies on the circumcircle of triangle $B D E$.

Let $D$ be the foot of perpendicular from $A$ to the Euler line (the line passing through the circumcentre and the orthocentre) of an acute scalene triangle $A B C$. A circle $\omega$ with centre $S$ passes through $A$ and $D$, and it intersects sides $A B$ and $A C$ at $X$ and $Y$ respectively. Let $P$ be the foot of altitude from $A$ to $B C$, and let $M$ be the midpoint of $B C$. Prove that the circumcentre of triangle $X S Y$ is equidistant from $P$ and $M$.

Let $A B C D$ be a convex quadrilateral with $\angle A B C=\angle A D C<90^{\circ}$. The internal angle bisectors of $\angle A B C$ and $\angle A D C$ meet $A C$ at $E$ and $F$ respectively, and meet each other at point $P$. Let $M$ be the midpoint of $A C$ and let $\omega$ be the circumcircle of triangle $B P D$. Segments $B M$ and $D M$ intersect $\omega$ again at $X$ and $Y$ respectively. Denote by $Q$ the intersection point of lines $X E$ and $Y F$. Prove that $P Q \perp A C$.

Let $I$ be the incentre of a non-equilateral triangle $A B C, I_{A}$ be the $A$-excentre, $I_{A}^{\prime}$ be the reflection of $I_{A}$ in $B C$, and $l_{A}$ be the reflection of line $A I_{A}^{\prime}$ in $A I$. Define points $I_{B}, I_{B}^{\prime}$ and line $l_{B}$ analogously. Let $P$ be the intersection point of $l_{A}$ and $l_{B}$. (a) Prove that $P$ lies on line $O I$ where $O$ is the circumcentre of triangle $A B C$. (b) Let one of the tangents from $P$ to the incircle of triangle $A B C$ meet the circumcircle at points $X$ and $Y$. Show that $\angle X I Y=120^{\circ}$.

Let $A_{1}, B_{1}$ and $C_{1}$ be points on sides $B C, C A$ and $A B$ of an acute triangle $A B C$ respectively, such that $A A_{1}, B B_{1}$ and $C C_{1}$ are the internal angle bisectors of triangle $A B C$. Let $I$ be the incentre of triangle $A B C$, and $H$ be the orthocentre of triangle $A_{1} B_{1} C_{1}$. Show that $$A H+B H+C H \geqslant A I+B I+C I$$

For any positive integer $k$, denote the sum of digits of $k$ in its decimal representation by $S(k)$. Find all polynomials $P(x)$ with integer coefficients such that for any positive integer $n \geqslant 2016$, the integer $P(n)$ is positive and $$S(P(n))=P(S(n))$$

Let $\tau(n)$ be the number of positive divisors of $n$. Let $\tau_{1}(n)$ be the number of positive divisors of $n$ which have remainders 1 when divided by 3 . Find all possible integral values of the fraction $\frac{\tau(10 n)}{\tau_{1}(10 n)}$.

Define $P(n)=n^{2}+n+1$. For any positive integers $a$ and $b$, the set $$\{P(a), P(a+1), P(a+2), \ldots, P(a+b)\}$$ is said to be fragrant if none of its elements is relatively prime to the product of the other elements. Determine the smallest size of a fragrant set.

Let $n, m, k$ and $l$ be positive integers with $n \neq 1$ such that $n^{k}+m n^{l}+1$ divides $n^{k+l}-1$. Prove that - $m=1$ and $l=2 k$; or - $l \mid k$ and $m=\frac{n^{k-l}-1}{n^{l}-1}$.

Let $a$ be a positive integer which is not a square number. Denote by $A$ the set of all positive integers $k$ such that $$k=\frac{x^{2}-a}{x^{2}-y^{2}}$$ for some integers $x$ and $y$ with $x>\sqrt{a}$. Denote by $B$ the set of all positive integers $k$ such that (1) is satisfied for some integers $x$ and $y$ with $0 \leqslant x<\sqrt{a}$. Prove that $A=B$.

Denote by $\mathbb{N}$ the set of all positive integers. Find all functions $f: \mathbb{N} \rightarrow \mathbb{N}$ such that for all positive integers $m$ and $n$, the integer $f(m)+f(n)-m n$ is nonzero and divides $m f(m)+n f(n)$.

Let $n$ be an odd positive integer. In the Cartesian plane, a cyclic polygon $P$ with area $S$ is chosen. All its vertices have integral coordinates, and all squares of its side lengths are divisible by $n$. Prove that $2 S$ is an integer divisible by $n$.

Find all polynomials $P(x)$ of odd degree $d$ and with integer coefficients satisfying the following property: for each positive integer $n$, there exist $n$ positive integers $x_{1}, x_{2}, \ldots, x_{n}$ such that $\frac{1}{2}<\frac{P\left(x_{i}\right)}{P\left(x_{j}\right)}<2$ and $\frac{P\left(x_{i}\right)}{P\left(x_{j}\right)}$ is the $d$-th power of a rational number for every pair of indices $i$ and $j$ with $1 \leqslant i, j \leqslant n$.