ISL 2019

Let $\mathbb{Z}$ be the set of integers. Determine all functions $f: \mathbb{Z} \rightarrow \mathbb{Z}$ such that, for all integers $a$ and $b$, $$f(2 a)+2 f(b)=f(f(a+b))$$ (South Africa)

Let $u_{1}, u_{2}, \ldots, u_{2019}$ be real numbers satisfying $$u_{1}+u_{2}+\cdots+u_{2019}=0 \text { and } u_{1}^{2}+u_{2}^{2}+\cdots+u_{2019}^{2}=1 .$$ Let $a=\min \left(u_{1}, u_{2}, \ldots, u_{2019}\right)$ and $b=\max \left(u_{1}, u_{2}, \ldots, u_{2019}\right)$. Prove that $$a b \leqslant-\frac{1}{2019}$$ (Germany)

Let $n \geqslant 3$ be a positive integer and let $\left(a_{1}, a_{2}, \ldots, a_{n}\right)$ be a strictly increasing sequence of $n$ positive real numbers with sum equal to 2 . Let $X$ be a subset of $\{1,2, \ldots, n\}$ such that the value of $$\left|1-\sum_{i \in X} a_{i}\right|$$ is minimised. Prove that there exists a strictly increasing sequence of $n$ positive real numbers $\left(b_{1}, b_{2}, \ldots, b_{n}\right)$ with sum equal to 2 such that $$\sum_{i \in X} b_{i}=1$$ (New Zealand) Common remarks. In all solutions, we say an index set $X$ is $\left(a_{i}\right)$-minimising if it has the property in the problem for the given sequence $\left(a_{i}\right)$. Write $X^{c}$ for the complement of $X$, and $[a, b]$ for the interval of integers $k$ such that $a \leqslant k \leqslant b$. Note that $$\left|1-\sum_{i \in X} a_{i}\right|=\left|1-\sum_{i \in X^{c}} a_{i}\right|,$$ so we may exchange $X$ and $X^{c}$ where convenient. Let $$\Delta=\sum_{i \in X^{c}} a_{i}-\sum_{i \in X} a_{i}$$ and note that $X$ is $\left(a_{i}\right)$-minimising if and only if it minimises $|\Delta|$, and that $\sum_{i \in X} a_{i}=1$ if and only if $\Delta=0$. In some solutions, a scaling process is used. If we have a strictly increasing sequence of positive real numbers $c_{i}$ (typically obtained by perturbing the $a_{i}$ in some way) such that $$\sum_{i \in X} c_{i}=\sum_{i \in X^{c}} c_{i}$$ then we may put $b_{i}=2 c_{i} / \sum_{j=1}^{n} c_{j}$. So it suffices to construct such a sequence without needing its sum to be 2 . The solutions below show various possible approaches to the problem. Solutions 1 and 2 perturb a few of the $a_{i}$ to form the $b_{i}$ (with scaling in the case of Solution 1, without scaling in the case of Solution 2). Solutions 3 and 4 look at properties of the index set $X$. Solution 3 then perturbs many of the $a_{i}$ to form the $b_{i}$, together with scaling. Rather than using such perturbations, Solution 4 constructs a sequence $\left(b_{i}\right)$ directly from the set $X$ with the required properties. Solution 4 can be used to give a complete description of sets $X$ that are $\left(a_{i}\right)$-minimising for some $\left(a_{i}\right)$.

Let $n \geqslant 2$ be a positive integer and $a_{1}, a_{2}, \ldots, a_{n}$ be real numbers such that $$a_{1}+a_{2}+\cdots+a_{n}=0$$ Define the set $A$ by $$A=\left\{(i, j)\left|1 \leqslant i<j \leqslant n,\left|a_{i}-a_{j}\right| \geqslant 1\right\} .\right.$$ Prove that, if $A$ is not empty, then $$\sum_{(i, j) \in A} a_{i} a_{j}<0$$ (China)

Let $x_{1}, x_{2}, \ldots, x_{n}$ be different real numbers. Prove that $$\sum_{1 \leqslant i \leqslant n} \prod_{j \neq i} \frac{1-x_{i} x_{j}}{x_{i}-x_{j}}= \begin{cases}0, & \text { if } n \text { is even } \\ 1, & \text { if } n \text { is odd }\end{cases}$$

A polynomial $P(x, y, z)$ in three variables with real coefficients satisfies the identities $$P(x, y, z)=P(x, y, x y-z)=P(x, z x-y, z)=P(y z-x, y, z) .$$ Prove that there exists a polynomial $F(t)$ in one variable such that $$P(x, y, z)=F\left(x^{2}+y^{2}+z^{2}-x y z\right) .$$

Let $\mathbb{Z}$ be the set of integers. We consider functions $f: \mathbb{Z} \rightarrow \mathbb{Z}$ satisfying $$f(f(x+y)+y)=f(f(x)+y)$$ for all integers $x$ and $y$. For such a function, we say that an integer $v$ is $f$-rare if the set $$X_{v}=\{x \in \mathbb{Z}: f(x)=v\}$$ is finite and nonempty. (a) Prove that there exists such a function $f$ for which there is an $f$-rare integer. (b) Prove that no such function $f$ can have more than one $f$-rare integer.

The infinite sequence $a_{0}, a_{1}, a_{2}, \ldots$ of (not necessarily different) integers has the following properties: $0 \leqslant a_{i} \leqslant i$ for all integers $i \geqslant 0$, and $$\binom{k}{a_{0}}+\binom{k}{a_{1}}+\cdots+\binom{k}{a_{k}}=2^{k}$$ for all integers $k \geqslant 0$. Prove that all integers $N \geqslant 0$ occur in the sequence (that is, for all $N \geqslant 0$, there exists $i \geqslant 0$ with $a_{i}=N$ ).

You are given a set of $n$ blocks, each weighing at least 1 ; their total weight is $2 n$. Prove that for every real number $r$ with $0 \leqslant r \leqslant 2 n-2$ you can choose a subset of the blocks whose total weight is at least $r$ but at most $r+2$. (Thailand)

Let $n$ be a positive integer. Harry has $n$ coins lined up on his desk, each showing heads or tails. He repeatedly does the following operation: if there are $k$ coins showing heads and $k>0$, then he flips the $k^{\text {th }}$ coin over; otherwise he stops the process. (For example, the process starting with THT would be THT $\rightarrow H H T \rightarrow H T T \rightarrow T T T$, which takes three steps.) Letting $C$ denote the initial configuration (a sequence of $n H$ 's and $T$ 's), write $\ell(C)$ for the number of steps needed before all coins show $T$. Show that this number $\ell(C)$ is finite, and determine its average value over all $2^{n}$ possible initial configurations $C$.

On a flat plane in Camelot, King Arthur builds a labyrinth $\mathfrak{L}$ consisting of $n$ walls, each of which is an infinite straight line. No two walls are parallel, and no three walls have a common point. Merlin then paints one side of each wall entirely red and the other side entirely blue. At the intersection of two walls there are four corners: two diagonally opposite corners where a red side and a blue side meet, one corner where two red sides meet, and one corner where two blue sides meet. At each such intersection, there is a two-way door connecting the two diagonally opposite corners at which sides of different colours meet. After Merlin paints the walls, Morgana then places some knights in the labyrinth. The knights can walk through doors, but cannot walk through walls. Let $k(\mathfrak{L})$ be the largest number $k$ such that, no matter how Merlin paints the labyrinth $\mathfrak{L}$, Morgana can always place at least $k$ knights such that no two of them can ever meet. For each $n$, what are all possible values for $k(\mathfrak{L})$, where $\mathfrak{L}$ is a labyrinth with $n$ walls? (Canada)

On a certain social network, there are 2019 users, some pairs of which are friends, where friendship is a symmetric relation. Initially, there are 1010 people with 1009 friends each and 1009 people with 1010 friends each. However, the friendships are rather unstable, so events of the following kind may happen repeatedly, one at a time: Let $A, B$, and $C$ be people such that $A$ is friends with both $B$ and $C$, but $B$ and $C$ are not friends; then $B$ and $C$ become friends, but $A$ is no longer friends with them. Prove that, regardless of the initial friendships, there exists a sequence of such events after which each user is friends with at most one other user. (Croatia)

Let $n>1$ be an integer. Suppose we are given $2 n$ points in a plane such that no three of them are collinear. The points are to be labelled $A_{1}, A_{2}, \ldots, A_{2 n}$ in some order. We then consider the $2 n$ angles $\angle A_{1} A_{2} A_{3}, \angle A_{2} A_{3} A_{4}, \ldots, \angle A_{2 n-2} A_{2 n-1} A_{2 n}, \angle A_{2 n-1} A_{2 n} A_{1}$, $\angle A_{2 n} A_{1} A_{2}$. We measure each angle in the way that gives the smallest positive value (i.e. between $0^{\circ}$ and $180^{\circ}$ ). Prove that there exists an ordering of the given points such that the resulting $2 n$ angles can be separated into two groups with the sum of one group of angles equal to the sum of the other group. Comment. The first three solutions all use the same construction involving a line separating the points into groups of $n$ points each, but give different proofs that this construction works. Although Solution 1 is very short, the Problem Selection Committee does not believe any of the solutions is easy to find and thus rates this as a problem of medium difficulty.

There are 60 empty boxes $B_{1}, \ldots, B_{60}$ in a row on a table and an unlimited supply of pebbles. Given a positive integer $n$, Alice and Bob play the following game. In the first round, Alice takes $n$ pebbles and distributes them into the 60 boxes as she wishes. Each subsequent round consists of two steps: (a) Bob chooses an integer $k$ with $1 \leqslant k \leqslant 59$ and splits the boxes into the two groups $B_{1}, \ldots, B_{k}$ and $B_{k+1}, \ldots, B_{60}$. (b) Alice picks one of these two groups, adds one pebble to each box in that group, and removes one pebble from each box in the other group. Bob wins if, at the end of any round, some box contains no pebbles. Find the smallest $n$ such that Alice can prevent Bob from winning. (Czech Republic)

Alice has a map of Wonderland, a country consisting of $n \geqslant 2$ towns. For every pair of towns, there is a narrow road going from one town to the other. One day, all the roads are declared to be "one way" only. Alice has no information on the direction of the roads, but the King of Hearts has offered to help her. She is allowed to ask him a number of questions. For each question in turn, Alice chooses a pair of towns and the King of Hearts tells her the direction of the road connecting those two towns. Alice wants to know whether there is at least one town in Wonderland with at most one outgoing road. Prove that she can always find out by asking at most $4 n$ questions. Comment. This problem could be posed with an explicit statement about points being awarded for weaker bounds $c n$ for some $c>4$, in the style of IMO 2014 Problem 6. (Thailand)

For any two different real numbers $x$ and $y$, we define $D(x, y)$ to be the unique integer $d$ satisfying $2^{d} \leqslant|x-y|<2^{d+1}$. Given a set of reals $\mathcal{F}$, and an element $x \in \mathcal{F}$, we say that the scales of $x$ in $\mathcal{F}$ are the values of $D(x, y)$ for $y \in \mathcal{F}$ with $x \neq y$. Let $k$ be a given positive integer. Suppose that each member $x$ of $\mathcal{F}$ has at most $k$ different scales in $\mathcal{F}$ (note that these scales may depend on $x$ ). What is the maximum possible size of $\mathcal{F}$ ? (Italy)

Let $A B C$ be a triangle. Circle $\Gamma$ passes through $A$, meets segments $A B$ and $A C$ again at points $D$ and $E$ respectively, and intersects segment $B C$ at $F$ and $G$ such that $F$ lies between $B$ and $G$. The tangent to circle $B D F$ at $F$ and the tangent to circle $C E G$ at $G$ meet at point $T$. Suppose that points $A$ and $T$ are distinct. Prove that line $A T$ is parallel to $B C$. (Nigeria)

Let $A B C$ be an acute-angled triangle and let $D, E$, and $F$ be the feet of altitudes from $A, B$, and $C$ to sides $B C, C A$, and $A B$, respectively. Denote by $\omega_{B}$ and $\omega_{C}$ the incircles of triangles $B D F$ and $C D E$, and let these circles be tangent to segments $D F$ and $D E$ at $M$ and $N$, respectively. Let line $M N$ meet circles $\omega_{B}$ and $\omega_{C}$ again at $P \neq M$ and $Q \neq N$, respectively. Prove that $M P=N Q$. (Vietnam)

In triangle $A B C$, let $A_{1}$ and $B_{1}$ be two points on sides $B C$ and $A C$, and let $P$ and $Q$ be two points on segments $A A_{1}$ and $B B_{1}$, respectively, so that line $P Q$ is parallel to $A B$. On ray $P B_{1}$, beyond $B_{1}$, let $P_{1}$ be a point so that $\angle P P_{1} C=\angle B A C$. Similarly, on ray $Q A_{1}$, beyond $A_{1}$, let $Q_{1}$ be a point so that $\angle C Q_{1} Q=\angle C B A$. Show that points $P, Q, P_{1}$, and $Q_{1}$ are concyclic. (Ukraine)

Let $P$ be a point inside triangle $A B C$. Let $A P$ meet $B C$ at $A_{1}$, let $B P$ meet $C A$ at $B_{1}$, and let $C P$ meet $A B$ at $C_{1}$. Let $A_{2}$ be the point such that $A_{1}$ is the midpoint of $P A_{2}$, let $B_{2}$ be the point such that $B_{1}$ is the midpoint of $P B_{2}$, and let $C_{2}$ be the point such that $C_{1}$ is the midpoint of $P C_{2}$. Prove that points $A_{2}, B_{2}$, and $C_{2}$ cannot all lie strictly inside the circumcircle of triangle $A B C$. (Australia)

Let $A B C D E$ be a convex pentagon with $C D=D E$ and $\angle E D C \neq 2 \cdot \angle A D B$. Suppose that a point $P$ is located in the interior of the pentagon such that $A P=A E$ and $B P=B C$. Prove that $P$ lies on the diagonal $C E$ if and only if $\operatorname{area}(B C D)+\operatorname{area}(A D E)=$ $\operatorname{area}(A B D)+\operatorname{area}(A B P)$. (Hungary)

Let $I$ be the incentre of acute-angled triangle $A B C$. Let the incircle meet $B C, C A$, and $A B$ at $D, E$, and $F$, respectively. Let line $E F$ intersect the circumcircle of the triangle at $P$ and $Q$, such that $F$ lies between $E$ and $P$. Prove that $\angle D P A+\angle A Q D=\angle Q I P$. (Slovakia)

The incircle $\omega$ of acute-angled scalene triangle $A B C$ has centre $I$ and meets sides $B C$, $C A$, and $A B$ at $D, E$, and $F$, respectively. The line through $D$ perpendicular to $E F$ meets $\omega$ again at $R$. Line $A R$ meets $\omega$ again at $P$. The circumcircles of triangles $P C E$ and $P B F$ meet again at $Q \neq P$. Prove that lines $D I$ and $P Q$ meet on the external bisector of angle $B A C$. (India) Common remarks. Throughout the solution, $\angle(a, b)$ denotes the directed angle between lines $a$ and $b$, measured modulo $\pi$.

Let $\mathcal{L}$ be the set of all lines in the plane and let $f$ be a function that assigns to each line $\ell \in \mathcal{L}$ a point $f(\ell)$ on $\ell$. Suppose that for any point $X$, and for any three lines $\ell_{1}, \ell_{2}, \ell_{3}$ passing through $X$, the points $f\left(\ell_{1}\right), f\left(\ell_{2}\right), f\left(\ell_{3}\right)$ and $X$ lie on a circle. Prove that there is a unique point $P$ such that $f(\ell)=P$ for any line $\ell$ passing through $P$. (Australia)

Find all pairs $(m, n)$ of positive integers satisfying the equation $$\left(2^{n}-1\right)\left(2^{n}-2\right)\left(2^{n}-4\right) \cdots\left(2^{n}-2^{n-1}\right)=m!$$ (El Salvador)

Find all triples $(a, b, c)$ of positive integers such that $a^{3}+b^{3}+c^{3}=(a b c)^{2}$. (Nigeria)

We say that a set $S$ of integers is rootiful if, for any positive integer $n$ and any $a_{0}, a_{1}, \ldots, a_{n} \in S$, all integer roots of the polynomial $a_{0}+a_{1} x+\cdots+a_{n} x^{n}$ are also in $S$. Find all rootiful sets of integers that contain all numbers of the form $2^{a}-2^{b}$ for positive integers $a$ and $b$. (Czech Republic)

Let $\mathbb{Z}_{>0}$ be the set of positive integers. A positive integer constant $C$ is given. Find all functions $f: \mathbb{Z}_{>0} \rightarrow \mathbb{Z}_{>0}$ such that, for all positive integers $a$ and $b$ satisfying $a+b>C$, $$a+f(b) \mid a^{2}+b f(a)$$ (Croatia)

Let $a$ be a positive integer. We say that a positive integer $b$ is $a$-good if $\binom{a n}{b}-1$ is divisible by $a n+1$ for all positive integers $n$ with $a n \geqslant b$. Suppose $b$ is a positive integer such that $b$ is $a$-good, but $b+2$ is not $a$-good. Prove that $b+1$ is prime. (Netherlands)

Let $H=\left\{\lfloor i \sqrt{2}\rfloor: i \in \mathbb{Z}_{>0}\right\}=\{1,2,4,5,7, \ldots\}$, and let $n$ be a positive integer. Prove that there exists a constant $C$ such that, if $A \subset\{1,2, \ldots, n\}$ satisfies $|A| \geqslant C \sqrt{n}$, then there exist $a, b \in A$ such that $a-b \in H$. (Brazil)

Prove that there is a constant $c>0$ and infinitely many positive integers $n$ with the following property: there are infinitely many positive integers that cannot be expressed as the sum of fewer than $c n \log (n)$ pairwise coprime $n^{\text {th }}$ powers. (Canada)

Let $a$ and $b$ be two positive integers. Prove that the integer $$a^{2}+\left\lceil\frac{4 a^{2}}{b}\right\rceil$$ is not a square. (Here $\lceil z\rceil$ denotes the least integer greater than or equal to $z$.)