13tn European Girls' Mathematical Olympiad (EGMO 2024)

Problem 6. 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) , P (2) , . . . , P ( d²− d ).

Solution

We claim that the answer is $d=1,2$ only which clearly work, now assume $d \geq 3$ . Firstly notice that if there are $\leq d-1$ distinct values then by lagrange interpolation the polynomial must be constant polynomial, and hence there will be exactly $d-1$ distinct values each appearing $d-1$ times while one value appearing $d$ times, now notice that scaling has no effect on the statement of the problem, WLOG $P(0)=P(a_1)=P(a_2)= \cdots = P(a_{d-2})=P(a_{d-1})=0$ ,(because we have $d$ equal values) so $P = x(x-a_1)(x-a_2)\cdots (x-a_{d-2})(x-a_{d-1})$ for non-negative integers $a_i$ . Let the other $d-1$ sequences be $B_1,B_2 \cdots B_{d-1}$ where $B_i = \{{B_i}_j\}$ where $j$ varies from $1$ to $d-1$ and let $P(B_i)=C_i$ then we have $\prod (x-{B_i}_j) \mid P(x)-C_i$ , let $S= a_1+a_2+ \cdots a_{d-1}$ , and therefore we have $P(x)=(\prod (x-{B_i}_j))(x-(S-\sum {B_i}_j))+C_i$ due to vieta's formulas and because $P$ is monic polynomial. Now, again by vieta's we have $(-1)^{d-1}(\prod {B_i}_j)(S-\sum {B_i}_j)=C_i$ now the idea is to put $x=S- \sum {B_i}_j$ and then again compare and do bounding to get $d=1,2$ .