Problem (Algebra):
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 \leq n$, and $k+1$ distinct integers $x_{1}, x_{2}, \ldots, x_{k+1}$ such that



$$

P\left(x_{1}\right)+P\left(x_{2}\right)+\cdots+P\left(x_{k}\right)=P\left(x_{k+1}\right) .

$$


Note. A polynomial is monic if the coefficient of the highest power is one.

Solution:
There is only one such integer, namely, $n=2$. In this case, if $P$ is a constant polynomial, the required condition is clearly satisfied; if $P=X+c$, then $P(c-1)+P(c+1)=$ $P(3 c)$; and if $P=X^{2}+q X+r$, then $P(X)=P(-X-q)$.



To rule out all other values of $n$, it is sufficient to exhibit a monic polynomial $P$ of degree at most $n$ with integer coefficients, whose restriction to the integers is injective, and $P(x) \equiv 1$ $(\bmod\  n)$ for all integers $x$. This is easily seen by reading the relation in the statement modulo $n$, to deduce that $k \equiv 1(\bmod\  n)$, so $k=1$, since $1 \leq k \leq n$; hence $P\left(x_{1}\right)=P\left(x_{2}\right)$ for some distinct integers $x_{1}$ and $x_{2}$, which contradicts injectivity.



If $n=1$, let $P=X$, and if $n=4$, let $P=X^{4}+7 X^{2}+4 X+1$. In the latter case, clearly, $P(x) \equiv 1(\bmod\  4)$ for all integers $x$; and $P$ is injective on the integers, since $P(x)-P(y)=$ $(x-y)\left((x+y)\left(x^{2}+y^{2}+7\right)+4\right)$, and the absolute value of $(x+y)\left(x^{2}+y^{2}+7\right)$ is either 0 or at least 7 for integral $x$ and $y$.



Assume henceforth $n \geq 3, n \neq 4$, and let $f_{n}=(X-1)(X-2) \cdots(X-n)$. Clearly, $f_{n}(x) \equiv$ $0(\bmod n)$ for all integers $x$. If $n$ is odd, then $f_{n}$ is non-decreasing on the integers; and if, in addition, $n>3$, then $f_{n}(x) \equiv 0(\bmod n+1)$ for all integers $x$, since $f_{n}(0)=-n !=-1 \cdot 2 \cdot \cdots$. $\frac{n+1}{2} \cdot \cdots \cdot n \equiv 0(\bmod\  n+1)$.



Finally, let $P=f_{n}+n X+1$ if $n$ is odd, and let $P=f_{n-1}+n X+1$ if $n$ is even. In either case, $P$ is strictly increasing, hence injective, on the integers, and $P(x) \equiv 1(\bmod n)$ for all integers $x$.

Final answer: 2