EGMO 2024

Problem. Two different integers $u$ and $v$ are written on a board. We perform a sequence of steps. At each step we do one of the following two operations: (i) If $a$ and $b$ are different integers on the board, then we can write $a+b$ on the board, if it is not already there. (ii) If $a, b$ and $c$ are three different integers on the board, and if an integer $x$ satisfies $a x^{2}+b x+c=0$, then we can write $x$ on the board, if it is not already there.

Determine all pairs of starting numbers $(u, v)$ from which any integer can eventually be written on the board after a finite sequence of steps.

Problem. For a sequence $a_{1}<a_{2}<\cdots<a_{n}$ of integers, a pair $\left(a_{i}, a_{j}\right)$ with $1 \leq i<j \leq n$ is called interesting if there exists a pair $\left(a_{k}, a_{l}\right)$ of integers with $1 \leq k<l \leq n$ such that

$$\frac{a_{l}-a_{k}}{a_{j}-a_{i}}=2$$

For each $n \geq 3$, find the largest possible number of interesting pairs in a sequence of length $n$.

Problem. Let $\mathbb{N}$ denote the set of positive integers. Find all functions $f: \mathbb{N} \rightarrow \mathbb{N}$ such that the following assertions are true for every pair of positive integers $(x, y)$ :

• $x$ and $f(x)$ have the same number of positive divisors.
• If $x$ does not divide $y$ and $y$ does not divide $x$, then

$$\operatorname{gcd}(f(x), f(y))>f(\operatorname{gcd}(x, y))$$

Here $\operatorname{gcd}(m, n)$ is the largest positive integer that divides both $m$ and $n$.

Problem. Find all positive integers $d$ for which there exists a degree $d$ polynomial $P$ with real coefficients such that there are at most $d$ different values among $P(0), P(1), \ldots, P\left(d^{2}-\right.$ d).

Remark 1 You can add a constant to a polynomial satisfying the conditions and obtain another polynomial satisfying the conditions.

Remark 2 This problem is equivalent to: Find all positive integers $d$ for which there exists a polynomial $P$ of degree $d$ that takes at most $d$ different values at members of a an arithmetic progression with $d^{2}-d+1$ (different) terms. The answer to this EGMO problem implies a solution to this more general problem by scaling and translating, and the general result solves the EGMO problem as a special case. This means that instead of working with $0,1, \ldots, d^{2}-d$ we have the option of working with a region that is symmetric about the origin. Irrespective of the parity of $d$ we can use the $d^{2}-d+1$ integers which run from $-\left(d^{2}-d\right) / 2$ to $\left(d^{2}-d\right) / 2$ inclusive.

The advantage of using an arithmetic progression which is symmetric about the 0 is that $P(X)$ is a polynomial which works for the problem if, and only if, $P(-X)$ is a polynomial which works for the problem. This means that working at one end of the run of integers is the reflection of the activity at the other end. T Remarks dismissing the cases at the other end of the run as similar now become obviously correct rather than having to be studied separately.