Zhukov G.

A teacher is planning 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) P\left(n_{2}\right) \ldots 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 such a problem so that the polynomial found by the children will definitely match the one thought of?
Evaluation. Let the teacher use some $k \leq 2016$, and consider the polynomial $P(x)$.

Consider the polynomial $P(x)=P(x)+\left(x-n_{1}\right)\left(x-n_{2}\right) \ldots\left(x-n_{k}\right)$. Notice that the degree of the polynomial $Q(x)$ is also

2017, and its leading coefficient is also 1. Moreover, $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)$

Thus, the children could have found the polynomial $Q(x)$ instead of $P(x)$, meaning the teacher did not achieve the required goal.

Example. 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.

Assume that some polynomial $Q(x)$ 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 such $i$ and $j$ 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 theorem of Bézout for integer polynomials (see problem $\underline{35562}$). Therefore, all values of $Q\left(n_{i}\right)$ are equal. However, all values cannot be equal to -1, since 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 $k$ distinct roots, meaning this polynomial is identically zero, and $P(x)=Q(x)$.

## Answer

For $k=2017$