ISL 2017

Let $a_{1}, a_{2}, \ldots, a_{n}, k$, and $M$ be positive integers such that $$\frac{1}{a_{1}}+\frac{1}{a_{2}}+\cdots+\frac{1}{a_{n}}=k \text { and } a_{1} a_{2} \ldots a_{n}=M$$ If $M>1$, prove that the polynomial $$P(x)=M(x+1)^{k}-\left(x+a_{1}\right)\left(x+a_{2}\right) \cdots\left(x+a_{n}\right)$$ has no positive roots. (Trinidad and Tobago)

Let $q$ be a real number. Gugu has a napkin with ten distinct real numbers written on it, and he writes the following three lines of real numbers on the blackboard: - In the first line, Gugu writes down every number of the form $a-b$, where $a$ and $b$ are two (not necessarily distinct) numbers on his napkin. - In the second line, Gugu writes down every number of the form qab, where $a$ and $b$ are two (not necessarily distinct) numbers from the first line. - In the third line, Gugu writes down every number of the form $a^{2}+b^{2}-c^{2}-d^{2}$, where $a, b, c, d$ are four (not necessarily distinct) numbers from the first line. Determine all values of $q$ such that, regardless of the numbers on Gugu's napkin, every number in the second line is also a number in the third line. (Austria)

Let $S$ be a finite set, and let $\mathcal{A}$ be the set of all functions from $S$ to $S$. Let $f$ be an element of $\mathcal{A}$, and let $T=f(S)$ be the image of $S$ under $f$. Suppose that $f \circ g \circ f \neq g \circ f \circ g$ for every $g$ in $\mathcal{A}$ with $g \neq f$. Show that $f(T)=T$. (India)

A sequence of real numbers $a_{1}, a_{2}, \ldots$ satisfies the relation $$a_{n}=-\max _{i+j=n}\left(a_{i}+a_{j}\right) \text { for all } n>2017$$ Prove that this sequence is bounded, i.e., there is a constant $M$ such that $\left|a_{n}\right| \leqslant M$ for all positive integers $n$. (Russia)

An integer $n \geqslant 3$ is given. We call an $n$-tuple of real numbers $\left(x_{1}, x_{2}, \ldots, x_{n}\right)$ Shiny if for each permutation $y_{1}, y_{2}, \ldots, y_{n}$ of these numbers we have $$\sum_{i=1}^{n-1} y_{i} y_{i+1}=y_{1} y_{2}+y_{2} y_{3}+y_{3} y_{4}+\cdots+y_{n-1} y_{n} \geqslant-1$$ Find the largest constant $K=K(n)$ such that $$\sum_{1 \leqslant i<j \leqslant n} x_{i} x_{j} \geqslant K$$ holds for every Shiny $n$-tuple $\left(x_{1}, x_{2}, \ldots, x_{n}\right)$.

Find all functions $f: \mathbb{R} \rightarrow \mathbb{R}$ such that $$f(f(x) f(y))+f(x+y)=f(x y)$$ for all $x, y \in \mathbb{R}$. (Albania)

Let $a_{0}, a_{1}, a_{2}, \ldots$ be a sequence of integers and $b_{0}, b_{1}, b_{2}, \ldots$ be a sequence of positive integers such that $a_{0}=0, a_{1}=1$, and $$a_{n+1}=\left\{\begin{array}{ll} a_{n} b_{n}+a_{n-1}, & \text { if } b_{n-1}=1 \\ a_{n} b_{n}-a_{n-1}, & \text { if } b_{n-1}>1 \end{array} \text { for } n=1,2, \ldots\right.$$ Prove that at least one of the two numbers $a_{2017}$ and $a_{2018}$ must be greater than or equal to 2017 . (Australia)

Assume that a function $f: \mathbb{R} \rightarrow \mathbb{R}$ satisfies the following condition: For every $x, y \in \mathbb{R}$ such that $(f(x)+y)(f(y)+x)>0$, we have $f(x)+y=f(y)+x$. Prove that $f(x)+y \leqslant f(y)+x$ whenever $x>y$. (Netherlands)

A rectangle $\mathcal{R}$ with odd integer side lengths is divided into small rectangles with integer side lengths. Prove that there is at least one among the small rectangles whose distances from the four sides of $\mathcal{R}$ are either all odd or all even. (Singapore)

Let $n$ be a positive integer. Define a chameleon to be any sequence of $3 n$ letters, with exactly $n$ occurrences of each of the letters $a, b$, and $c$. Define a swap to be the transposition of two adjacent letters in a chameleon. Prove that for any chameleon $X$, there exists a chameleon $Y$ such that $X$ cannot be changed to $Y$ using fewer than $3 n^{2} / 2$ swaps. (Australia)

Sir Alex plays the following game on a row of 9 cells. Initially, all cells are empty. In each move, Sir Alex is allowed to perform exactly one of the following two operations: (1) Choose any number of the form $2^{j}$, where $j$ is a non-negative integer, and put it into an empty cell. (2) Choose two (not necessarily adjacent) cells with the same number in them; denote that number by $2^{j}$. Replace the number in one of the cells with $2^{j+1}$ and erase the number in the other cell. At the end of the game, one cell contains the number $2^{n}$, where $n$ is a given positive integer, while the other cells are empty. Determine the maximum number of moves that Sir Alex could have made, in terms of $n$. (Thailand)

Let $N \geqslant 2$ be an integer. $N(N+1)$ soccer players, no two of the same height, stand in a row in some order. Coach Ralph wants to remove $N(N-1)$ people from this row so that in the remaining row of $2 N$ players, no one stands between the two tallest ones, no one stands between the third and the fourth tallest ones, ..., and finally no one stands between the two shortest ones. Show that this is always possible. (Russia)

A hunter and an invisible rabbit play a game in the Euclidean plane. The hunter's starting point $H_{0}$ coincides with the rabbit's starting point $R_{0}$. In the $n^{\text {th }}$ round of the game ( $n \geqslant 1$ ), the following happens. (1) First the invisible rabbit moves secretly and unobserved from its current point $R_{n-1}$ to some new point $R_{n}$ with $R_{n-1} R_{n}=1$. (2) The hunter has a tracking device (e.g. dog) that returns an approximate position $R_{n}^{\prime}$ of the rabbit, so that $R_{n} R_{n}^{\prime} \leqslant 1$. (3) The hunter then visibly moves from point $H_{n-1}$ to a new point $H_{n}$ with $H_{n-1} H_{n}=1$. Is there a strategy for the hunter that guarantees that after $10^{9}$ such rounds the distance between the hunter and the rabbit is below 100 ? (Austria)

Let $n>1$ be an integer. An $n \times n \times n$ cube is composed of $n^{3}$ unit cubes. Each unit cube is painted with one color. For each $n \times n \times 1$ box consisting of $n^{2}$ unit cubes (of any of the three possible orientations), we consider the set of the colors present in that box (each color is listed only once). This way, we get $3 n$ sets of colors, split into three groups according to the orientation. It happens that for every set in any group, the same set appears in both of the other groups. Determine, in terms of $n$, the maximal possible number of colors that are present. (Russia)

For any finite sets $X$ and $Y$ of positive integers, denote by $f_{X}(k)$ the $k^{\mathrm{th}}$ smallest positive integer not in $X$, and let $$X * Y=X \cup\left\{f_{X}(y): y \in Y\right\}$$ Let $A$ be a set of $a>0$ positive integers, and let $B$ be a set of $b>0$ positive integers. Prove that if $A * B=B * A$, then $$\underbrace{A *(A * \cdots *(A *(A * A)) \ldots)}_{A \text { appears } b \text { times }}=\underbrace{B *(B * \cdots *(B *(B * B)) \ldots)}_{B \text { appears } a \text { times }} .$$

Let $n$ be a given positive integer. In the Cartesian plane, each lattice point with nonnegative coordinates initially contains a butterfly, and there are no other butterflies. The neighborhood of a lattice point $c$ consists of all lattice points within the axis-aligned $(2 n+1) \times(2 n+1)$ square centered at $c$, apart from $c$ itself. We call a butterfly lonely, crowded, or comfortable, depending on whether the number of butterflies in its neighborhood $N$ is respectively less than, greater than, or equal to half of the number of lattice points in $N$. Every minute, all lonely butterflies fly away simultaneously. This process goes on for as long as there are any lonely butterflies. Assuming that the process eventually stops, determine the number of comfortable butterflies at the final state.

Let $A B C D E$ be a convex pentagon such that $A B=B C=C D, \angle E A B=\angle B C D$, and $\angle E D C=\angle C B A$. Prove that the perpendicular line from $E$ to $B C$ and the line segments $A C$ and $B D$ are concurrent. (Italy)

Let $R$ and $S$ be distinct points on circle $\Omega$, and let $t$ denote the tangent line to $\Omega$ at $R$. Point $R^{\prime}$ is the reflection of $R$ with respect to $S$. A point $I$ is chosen on the smaller arc $R S$ of $\Omega$ so that the circumcircle $\Gamma$ of triangle $I S R^{\prime}$ intersects $t$ at two different points. Denote by $A$ the common point of $\Gamma$ and $t$ that is closest to $R$. Line $A I$ meets $\Omega$ again at $J$. Show that $J R^{\prime}$ is tangent to $\Gamma$. (Luxembourg)

Let $O$ be the circumcenter of an acute scalene triangle $A B C$. Line $O A$ intersects the altitudes of $A B C$ through $B$ and $C$ at $P$ and $Q$, respectively. The altitudes meet at $H$. Prove that the circumcenter of triangle $P Q H$ lies on a median of triangle $A B C$. (Ukraine)

In triangle $A B C$, let $\omega$ be the excircle opposite $A$. Let $D, E$, and $F$ be the points where $\omega$ is tangent to lines $B C, C A$, and $A B$, respectively. The circle $A E F$ intersects line $B C$ at $P$ and $Q$. Let $M$ be the midpoint of $A D$. Prove that the circle $M P Q$ is tangent to $\omega$. (Denmark)

Let $A B C C_{1} B_{1} A_{1}$ be a convex hexagon such that $A B=B C$, and suppose that the line segments $A A_{1}, B B_{1}$, and $C C_{1}$ have the same perpendicular bisector. Let the diagonals $A C_{1}$ and $A_{1} C$ meet at $D$, and denote by $\omega$ the circle $A B C$. Let $\omega$ intersect the circle $A_{1} B C_{1}$ again at $E \neq B$. Prove that the lines $B B_{1}$ and $D E$ intersect on $\omega$. (Ukraine)

Let $n \geqslant 3$ be an integer. Two regular $n$-gons $\mathcal{A}$ and $\mathcal{B}$ are given in the plane. Prove that the vertices of $\mathcal{A}$ that lie inside $\mathcal{B}$ or on its boundary are consecutive. (That is, prove that there exists a line separating those vertices of $\mathcal{A}$ that lie inside $\mathcal{B}$ or on its boundary from the other vertices of $\mathcal{A}$.) (Czech Republic)

A convex quadrilateral $A B C D$ has an inscribed circle with center $I$. Let $I_{a}, I_{b}, I_{c}$, and $I_{d}$ be the incenters of the triangles $D A B, A B C, B C D$, and $C D A$, respectively. Suppose that the common external tangents of the circles $A I_{b} I_{d}$ and $C I_{b} I_{d}$ meet at $X$, and the common external tangents of the circles $B I_{a} I_{c}$ and $D I_{a} I_{c}$ meet at $Y$. Prove that $\angle X I Y=90^{\circ}$. (Kazakhstan)

There are 2017 mutually external circles drawn on a blackboard, such that no two are tangent and no three share a common tangent. A tangent segment is a line segment that is a common tangent to two circles, starting at one tangent point and ending at the other one. Luciano is drawing tangent segments on the blackboard, one at a time, so that no tangent segment intersects any other circles or previously drawn tangent segments. Luciano keeps drawing tangent segments until no more can be drawn. Find all possible numbers of tangent segments when he stops drawing. (Australia)

The sequence $a_{0}, a_{1}, a_{2}, \ldots$ of positive integers satisfies $$a_{n+1}=\left\{\begin{array}{ll} \sqrt{a_{n}}, & \text { if } \sqrt{a_{n}} \text { is an integer } \\ a_{n}+3, & \text { otherwise } \end{array} \text { for every } n \geqslant 0\right.$$ Determine all values of $a_{0}>1$ for which there is at least one number $a$ such that $a_{n}=a$ for infinitely many values of $n$. (South Africa)

Let $p \geqslant 2$ be a prime number. Eduardo and Fernando play the following game making moves alternately: in each move, the current player chooses an index $i$ in the set $\{0,1, \ldots, p-1\}$ that was not chosen before by either of the two players and then chooses an element $a_{i}$ of the set $\{0,1,2,3,4,5,6,7,8,9\}$. Eduardo has the first move. The game ends after all the indices $i \in\{0,1, \ldots, p-1\}$ have been chosen. Then the following number is computed: $$M=a_{0}+10 \cdot a_{1}+\cdots+10^{p-1} \cdot a_{p-1}=\sum_{j=0}^{p-1} a_{j} \cdot 10^{j}$$ The goal of Eduardo is to make the number $M$ divisible by $p$, and the goal of Fernando is to prevent this. Prove that Eduardo has a winning strategy. (Morocco)

Determine all integers $n \geqslant 2$ with the following property: for any integers $a_{1}, a_{2}, \ldots, a_{n}$ whose sum is not divisible by $n$, there exists an index $1 \leqslant i \leqslant n$ such that none of the numbers $$a_{i}, a_{i}+a_{i+1}, \ldots, a_{i}+a_{i+1}+\cdots+a_{i+n-1}$$ is divisible by $n$. (We let $a_{i}=a_{i-n}$ when $i>n$.) (Thailand)

Call a rational number short if it has finitely many digits in its decimal expansion. For a positive integer $m$, we say that a positive integer $t$ is $m$-tastic if there exists a number $c \in\{1,2,3, \ldots, 2017\}$ such that $\frac{10^{t}-1}{c \cdot m}$ is short, and such that $\frac{10^{k}-1}{c \cdot m}$ is not short for any $1 \leqslant k<t$. Let $S(m)$ be the set of $m$-tastic numbers. Consider $S(m)$ for $m=1,2, \ldots$. What is the maximum number of elements in $S(m)$ ? (Turkey)

Find all pairs $(p, q)$ of prime numbers with $p>q$ for which the number $$\frac{(p+q)^{p+q}(p-q)^{p-q}-1}{(p+q)^{p-q}(p-q)^{p+q}-1}$$ is an integer.

Find the smallest positive integer $n$, or show that no such $n$ exists, with the following property: there are infinitely many distinct $n$-tuples of positive rational numbers ( $a_{1}, a_{2}, \ldots, a_{n}$ ) such that both $$a_{1}+a_{2}+\cdots+a_{n} \text { and } \frac{1}{a_{1}}+\frac{1}{a_{2}}+\cdots+\frac{1}{a_{n}}$$ are integers. (Singapore)

Say that an ordered pair $(x, y)$ of integers is an irreducible lattice point if $x$ and $y$ are relatively prime. For any finite set $S$ of irreducible lattice points, show that there is a homogenous polynomial in two variables, $f(x, y)$, with integer coefficients, of degree at least 1 , such that $f(x, y)=1$ for each $(x, y)$ in the set $S$. Note: A homogenous polynomial of degree $n$ is any nonzero polynomial of the form $$f(x, y)=a_{0} x^{n}+a_{1} x^{n-1} y+a_{2} x^{n-2} y^{2}+\cdots+a_{n-1} x y^{n-1}+a_{n} y^{n} .$$

Let $p$ be an odd prime number and $\mathbb{Z}_{>0}$ be the set of positive integers. Suppose that a function $f: \mathbb{Z}_{>0} \times \mathbb{Z}_{>0} \rightarrow\{0,1\}$ satisfies the following properties: - $f(1,1)=0$; - $f(a, b)+f(b, a)=1$ for any pair of relatively prime positive integers $(a, b)$ not both equal to 1 ; - $f(a+b, b)=f(a, b)$ for any pair of relatively prime positive integers $(a, b)$. Prove that $$\sum_{n=1}^{p-1} f\left(n^{2}, p\right) \geqslant \sqrt{2 p}-2$$