Olympiad problems

2019 IMO Shortlist, G4

Let $P$ be a point inside triangle $ABC$. Let $AP$ meet $BC$ at $A_1$, let $BP$ meet $CA$ at $B_1$, and let $CP$ meet $AB$ at $C_1$. Let $A_2$ be the point such that $A_1$ is the midpoint of $PA_2$, let $B_2$ be the point such that $B_1$ is the midpoint of $PB_2$, and let $C_2$ be the point such that $C_1$ is the midpoint of $PC_2$. Prove that points $A_2, B_2$, and $C_2$ cannot all lie strictly inside the circumcircle of triangle $ABC$. (Australia)

2020 Thailand TST, 6

Tags: combinatorics , IMO Shortlist , IMO Shortlist 2019 , game , Combinatorial games

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\leq k\leq 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. [i]Czech Republic[/i]

2020 Thailand TST, 5

Tags: number theory , IMO Shortlist , IMO Shortlist 2019 , polynomial

We say that a set $S$ of integers is [i]rootiful[/i] if, for any positive integer $n$ and any $a_0, a_1, \cdots, a_n \in S$, all integer roots of the polynomial $a_0+a_1x+\cdots+a_nx^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$.

2020 Thailand TST, 6

Tags: geometry , IMO Shortlist , IMO Shortlist 2019 , functional-geometry

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(\ell_1),f(\ell_2),f(\ell_3)$, 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$. [i]Australia[/i]

2020 Germany Team Selection Test, 2

Tags: geometry , IMO Shortlist , IMO Shortlist 2019 , Triangle

Let $P$ be a point inside triangle $ABC$. Let $AP$ meet $BC$ at $A_1$, let $BP$ meet $CA$ at $B_1$, and let $CP$ meet $AB$ at $C_1$. Let $A_2$ be the point such that $A_1$ is the midpoint of $PA_2$, let $B_2$ be the point such that $B_1$ is the midpoint of $PB_2$, and let $C_2$ be the point such that $C_1$ is the midpoint of $PC_2$. Prove that points $A_2, B_2$, and $C_2$ cannot all lie strictly inside the circumcircle of triangle $ABC$. (Australia)

2019 IMO Shortlist, N7

Tags: number theory , IMO Shortlist , IMO Shortlist 2019 , Additive Number Theory

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 $cn\log(n)$ pairwise coprime $n$th powers. [i]Canada[/i]

2020 Germany Team Selection Test, 1

Tags: IMO Shortlist , IMO Shortlist 2019 , combinatorics , induction , Local argument

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

2020 Taiwan TST Round 1, 4

Tags: algebra , IMO Shortlist , IMO Shortlist 2019 , inequalities

Let $u_1, u_2, \dots, 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}. \]

2020 Taiwan TST Round 3, 1

Tags: algebra , Product , IMO Shortlist , IMO Shortlist 2019 , determinant

Let $x_1, x_2, \dots, 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}}=\left\{\begin{array}{ll} 0, & \text { if } n \text { is even; } \\ 1, & \text { if } n \text { is odd. } \end{array}\right.\]

2020 Azerbaijan IMO TST, 3

Tags: IMO Shortlist , IMO Shortlist 2019 , number theory

Let $a$ be a positive integer. We say that a positive integer $b$ is [i]$a$-good[/i] if $\tbinom{an}{b}-1$ is divisible by $an+1$ for all positive integers $n$ with $an \geq 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.

2019 IMO Shortlist, C5

Tags: combinatorics , IMO 2019 , IMO , graph theory , reachability , termination , IMO Shortlist 2019

A social network has $2019$ users, some pairs of whom are friends. Whenever user $A$ is friends with user $B$, user $B$ is also friends with user $A$. Events of the following kind may happen repeatedly, one at a time: [list] [*] Three users $A$, $B$, and $C$ such that $A$ is friends with both $B$ and $C$, but $B$ and $C$ are not friends, change their friendship statuses such that $B$ and $C$ are now friends, but $A$ is no longer friends with $B$, and no longer friends with $C$. All other friendship statuses are unchanged. [/list] Initially, $1010$ users have $1009$ friends each, and $1009$ users have $1010$ friends each. Prove that there exists a sequence of such events after which each user is friends with at most one other user. [i]Proposed by Adrian Beker, Croatia[/i]

2019 IMO Shortlist, G8

Tags: geometry , IMO Shortlist , IMO Shortlist 2019 , functional-geometry

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(\ell_1),f(\ell_2),f(\ell_3)$, 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$. [i]Australia[/i]

2019 IMO Shortlist, A2

Tags: algebra , IMO Shortlist , IMO Shortlist 2019 , inequalities

Let $u_1, u_2, \dots, 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}. \]

2019 IMO Shortlist, N4

Tags: number theory , IMO Shortlist , IMO Shortlist 2019 , functional equation , Hi

Find all functions $f:\mathbb Z_{>0}\to \mathbb Z_{>0}$ such that $a+f(b)$ divides $a^2+bf(a)$ for all positive integers $a$ and $b$ with $a+b>2019$.

2020 Azerbaijan IMO TST, 1

Tags: algebra , IMO Shortlist , IMO Shortlist 2019 , inequalities

Let $u_1, u_2, \dots, 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}. \]

2020 Greece Team Selection Test, 4

Tags: ceiling function , number theory , IMO Shortlist , IMO Shortlist 2019 , Perfect Square

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

Russian TST 2020, P3

Tags: IMO Shortlist , algebra , polynomial , IMO Shortlist 2019

A polynomial $P(x, y, z)$ in three variables with real coefficients satisfies the identities $$P(x, y, z)=P(x, y, xy-z)=P(x, zx-y, z)=P(yz-x, y, z).$$ Prove that there exists a polynomial $F(t)$ in one variable such that $$P(x,y,z)=F(x^2+y^2+z^2-xyz).$$

2019 IMO, 5

Tags: IMO 2019 , combinatorics , IMO Shortlist , IMO Shortlist 2019 , IMO

The Bank of Bath issues coins with an $H$ on one side and a $T$ on the other. Harry has $n$ of these coins arranged in a line from left to right. He repeatedly performs the following operation: if there are exactly $k>0$ coins showing $H$, then he turns over the $k$th coin from the left; otherwise, all coins show $T$ and he stops. For example, if $n=3$ the process starting with the configuration $THT$ would be $THT \to HHT \to HTT \to TTT$, which stops after three operations. (a) Show that, for each initial configuration, Harry stops after a finite number of operations. (b) For each initial configuration $C$, let $L(C)$ be the number of operations before Harry stops. For example, $L(THT) = 3$ and $L(TTT) = 0$. Determine the average value of $L(C)$ over all $2^n$ possible initial configurations $C$. [i]Proposed by David Altizio, USA[/i]

2020 Germany Team Selection Test, 1

Tags: algebra , IMO Shortlist , IMO Shortlist 2019 , inequalities

Let $u_1, u_2, \dots, 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}. \]

2020 Thailand TST, 4

Tags: algebra , IMO Shortlist , IMO Shortlist 2019 , inequalities

Let $u_1, u_2, \dots, 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}. \]

2019 IMO Shortlist, N5

Tags: IMO Shortlist , IMO Shortlist 2019 , number theory

Let $a$ be a positive integer. We say that a positive integer $b$ is [i]$a$-good[/i] if $\tbinom{an}{b}-1$ is divisible by $an+1$ for all positive integers $n$ with $an \geq 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.

2020 Greece Team Selection Test, 3

Tags: combinatorics , binomial coefficients , IMO Shortlist , IMO Shortlist 2019 , trivial , Hi

The infinite sequence $a_0,a _1, a_2, \dots$ of (not necessarily distinct) integers has the following properties: $0\le a_i \le i$ for all integers $i\ge 0$, and \[\binom{k}{a_0} + \binom{k}{a_1} + \dots + \binom{k}{a_k} = 2^k\] for all integers $k\ge 0$. Prove that all integers $N\ge 0$ occur in the sequence (that is, for all $N\ge 0$, there exists $i\ge 0$ with $a_i=N$).

2020 SAFEST Olympiad, 1

Tags: IMO Shortlist , IMO Shortlist 2019 , combinatorics , induction , Local argument

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

2020 Germany Team Selection Test, 2

Tags: geometry , IMO Shortlist , IMO Shortlist 2019 , Triangle

Let $P$ be a point inside triangle $ABC$. Let $AP$ meet $BC$ at $A_1$, let $BP$ meet $CA$ at $B_1$, and let $CP$ meet $AB$ at $C_1$. Let $A_2$ be the point such that $A_1$ is the midpoint of $PA_2$, let $B_2$ be the point such that $B_1$ is the midpoint of $PB_2$, and let $C_2$ be the point such that $C_1$ is the midpoint of $PC_2$. Prove that points $A_2, B_2$, and $C_2$ cannot all lie strictly inside the circumcircle of triangle $ABC$. (Australia)

2019 IMO Shortlist, A5

Tags: algebra , Product , IMO Shortlist , IMO Shortlist 2019 , determinant

Let $x_1, x_2, \dots, 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}}=\left\{\begin{array}{ll} 0, & \text { if } n \text { is even; } \\ 1, & \text { if } n \text { is odd. } \end{array}\right.\]