10.4. The teacher is going to give the children a problem of the following type. He will inform them that he has thought of a polynomial $P(x)$ of degree 2017 with integer coefficients, the leading coefficient of which is 1. Then he will tell them $k$ integers $n_{1}, n_{2}, \ldots, n_{k}$, and separately inform them of the value of the expression $P\left(n_{1}\right) \cdot P\left(n_{2}\right) \cdot \ldots \cdot P\left(n_{k}\right)$. Based on this data, the children are supposed to find the polynomial that the teacher could have thought of. For what smallest $k$ can the teacher formulate a problem of this type so that the polynomial found by the children necessarily coincides with the one thought of?

(G. Zhukov)
Answer. For $k=2017$.

Solution. First, we prove that $k>2016$. Suppose the teacher used some $k \leqslant 2016$, thinking of the polynomial $P(x)$. Consider the polynomial $Q(x)=P(x)+\left(x-n_{1}\right)\left(x-n_{2}\right) \ldots(x-n_{k})$. Note that the degree of the polynomial $Q(x)$ is also 2017, and its leading coefficient is also 1. Meanwhile, $P\left(n_{1}\right) P\left(n_{2}\right) \ldots P\left(n_{k}\right)=Q\left(n_{1}\right) Q\left(n_{2}\right) \ldots Q\left(n_{k}\right)$, but $P(x) \neq Q(x)$. Therefore, the children could have found the polynomial $Q(x)$ instead of $P(x)$, meaning the teacher did not achieve the required result.

It remains to prove that for $k=2017$ the teacher can come up with the required problem.

Lemma. Let $P(x)$ be a polynomial with integer coefficients, and let $a$ and $b$ be different integers. Then $P(a)-P(b)$ is divisible by $a-b$.

Proof. In the difference $P(a)-P(b)$, we group the terms by powers: if $P(x)=p_{n} x^{n}+p_{n-1} x^{n-1}+\ldots+p_{1} x+p_{0}$, then $P(a)-P(b)=p_{n}\left(a^{n}-b^{n}\right)+p_{n-1}\left(a^{n-1}-b^{n-1}\right)+\ldots+p_{1}(a-b)$, where each term is divisible by $a-b$.

Let $k=2017$. Set $n_{i}=4 i$ for $i=1,2, \ldots, k$; suppose the teacher informs the children that $P\left(n_{1}\right) P\left(n_{2}\right) \ldots P\left(n_{k}\right)=1$. Then the polynomial $P(x)=\left(x-n_{1}\right)\left(x-n_{2}\right) \ldots\left(x-n_{k}\right)+1$ fits the condition. Suppose there is another polynomial $Q(x)$ that also fits the condition. Then, since $Q\left(n_{1}\right) Q\left(n_{2}\right) \ldots Q\left(n_{k}\right)=1$ and the coefficients of the polynomial $Q(x)$ are integers, $Q\left(n_{i}\right)= \pm 1$ for any $i=1,2, \ldots, k$.

If there exist $i$ and $j$ such that $Q\left(n_{i}\right)=1$ and $Q\left(n_{j}\right)=-1$, then the difference $Q\left(n_{i}\right)-Q\left(n_{j}\right)=2$ is not divisible by $n_{i}-n_{j}$, which contradicts the lemma. Therefore, all values $Q\left(n_{i}\right)$ are equal to each other and are all equal to either 1 or -1. However, all values cannot be -1, as the product $Q\left(n_{1}\right) Q\left(n_{2}\right) \ldots Q\left(n_{k}\right)$ has an odd number of factors and the product would be -1. Thus, $Q\left(n_{i}\right)=1$ for any $i=1,2, \ldots, k$. Then the difference $P(x)-Q(x)$ is a polynomial of degree less than $k$, having at least $k$ roots, meaning this polynomial is identically zero, and $P(x)=Q(x)$. Contradiction.

Remark. Using the lemma, it can be shown that the polynomial $P(x)=\left(x-n_{1}\right)\left(x-n_{2}\right) \ldots\left(x-n_{2017}\right) \pm 1$ fits for any different integers $n_{1}, n_{2}, \ldots, n_{2017}$.

Comment. Only the correct answer - 0 points.

A complete solution to the problem consists of two parts:

(a) proving that the required cannot be achieved for $k \leqslant 2016$ - evaluated out of 2 points;

(b) proving that for $k=2017$ the required can be achieved - evaluated out of 5 points.

If in part (b) the polynomial $P(x)=\left(x-n_{1}\right)(x-n_{2}) \ldots\left(x-n_{k}\right) \pm 1$ (for some different integers $n_{1}, n_{2}, \ldots, n_{k}$) is presented, but it is not proven that no other polynomial $Q(x)$ satisfies the condition - 2 points (out of five).

Using the lemma about the divisibility of $P(a)-P(b)$ by $a-b$ without proof does not result in point deductions.