2017 Romanian Masters In Mathematics #2

Determine all positive integers $n$ satisfying the following condition: for every monic polynomial $P$ of degree at most $n$ with integer coefficients, there exists a positive integer $k\le n$ and $k+1$ distinct integers $x_1,x_2,\cdots ,x_{k+1}$ such that\[P(x_1)+P(x_2)+\cdots +P(x_k)=P(x_{k+1})\]

The answer is $\boxed{n = 2}$ only.

First, we show the result holds for $n = 2$. The result is immediate if $\deg P = 0$ (take $k=1$) or $\deg P = 1$ (take $k=2$). For $\deg P = 2$, we note the polynomials $P(x) = x^2+bx+c$ work for $k=1$.

Next note that the result is obviously false for $n = 1$, as that would make $k$ nonpositive.

Finally, the main part: we show that each fixed $n \ge 3$ does not work. Select a prime $p > 2$ such that $p \le n \le 2p$ (by Bertrand postulate). Then, consider the polynomial

\[ P(x) = x^p + (2p-1)x + 1. \]We have $P(x) \equiv 1 \pmod p$ and $P(x) \equiv 1 \pmod 2$ for every $x \in \mathbb Z$, whence $P(x) \equiv 1 \pmod{2p}$. Thus if such $x_i$ exist we have

\[ \underbrace{1 + \dots + 1}_k \equiv 1 \pmod{2p} \]and so $2p \mid k-1$, but from $k \le n$ we conclude $k = 1$.

This means there must be integers $a \neq b$ such that $P(a) = P(b)$, whence\[ \frac{a^p - b^p}{a-b} = -(2p-1) \]which is impossible since the left-hand side is always positive (for $a \neq b$).