Question bank IMO Shortlist 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))
$$

Let $u_{1}, u_{2}, \ldots, u_{2019}$ be real numbers satisfying

$$
u_{1}+u_{2}+\cdots+u_{2019}=0 \quad \text { and } \quad 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}
$$

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
$$

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\lt 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}\lt 0
$$

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 $\left.a_{i}=N\right)$.

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$.

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\gt 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?

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.

Let $n\gt 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.

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\gt 4$, in the style of IMO 2014 Problem 6.

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|\lt 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}$ ?

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$.

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$.

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.

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$.