EGMO 2024 Problem 6

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.