1. Determine all natural numbers $n$ for which there exists a polynomial $P_{n}(x)$ of degree $n$ with integer coefficients, such that it equals $n$ at $n$ different integer values, and equals zero at zero.
Solution. The polynomial $Q_{n}(x)=n-P_{n}(x)$ is also of $n$-th degree, but such that it is equal to zero at $n$ different integer points, and at zero it is equal to $n$. According to this,

$$
Q_{n}(x)=a\left(x-x_{1}\right)\left(x-x_{2}\right) \ldots\left(x-x_{n}\right)
$$

where $x_{1}, x_{2}, \ldots, x_{n}$ are the roots of the polynomial $Q_{n}(x)$. From Vieta's formulas it follows that

$$
n=Q_{n}(0)=(-1)^{n} a x_{1} x_{2} \ldots x_{n}
$$

and since among the roots $x_{1}, x_{2}, \ldots, x_{n}$ at most two are equal to 1 or -1, from equation (1) it follows that

$$
\left|(-1)^{n} a x_{1} x_{2} \ldots x_{n}\right| \geq 2^{n-2}
$$

From (1) and (2) we get $n \geq 2^{n-2}$. The last inequality is satisfied for $n \leq 4$ (by induction it can be proved that for $n>4$ we have $2^{n-2}>n$). Therefore, for $n=0,1,2,3,4$ the required polynomials may exist. For example, these are the polynomials

$$
\begin{aligned}
& Q_{0}(x)=0=P_{0}(x) \\
& Q_{1}(x)=x+1, P_{1}(x)=-x \\
& Q_{2}(x)=(x-1)(x-2), P_{2}(x)=3 x-x^{2} \\
& Q_{3}(x)=(x-1)(x+1)(x-3), P_{3}(x)=x+3 x^{2}-x^{3} \\
& Q_{4}(x)=(x-1)(x+1)(x-2)(x+2), P_{4}(x)=5 x^{2}-x^{4}
\end{aligned}
$$