Let $\Gamma$.

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 inform them of $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)$. From 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?
Evaluation. Let the teacher use some $k \leq 2016$, thinking of a 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. In this case, $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)$.

This means that the children could have found the polynomial $Q(x)$ instead of $P(x)$, so 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.

Suppose 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 Bezout 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, because in the product $Q\left(n_{1}\right) Q\left(n_{2}\right) \ldots Q\left(n_{k}\right)$ there is 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, so this polynomial is identically zero, and $P(x)=Q(x)$.

## Answer

For $k=2017$.

Author: Antipov M.

Each cell of a $100 \times 100$ board is colored either black or white, and all cells adjacent to the board's border are black. It turns out that there is no monochromatic $2 \times 2$ square anywhere on the board. Prove that there is a $2 \times 2$ square on the board whose cells are colored in a checkerboard pattern.

## Solution

Assume the opposite: there are no monochromatic or checkerboard-patterned $2 \times 2$ squares on the board. Consider all segments of the grid that separate two cells of different colors (call them separators); let their number be $N$.

In any $2 \times 2$ square, there is either exactly one cell of one color and three cells of the other, or two adjacent white cells and two adjacent black cells. In both cases, there are exactly two separators inside the square. There are a total of $99^{2}$ $2 \times 2$ squares, and each separator lies inside exactly two of them (by the condition, separators do not touch the border). Therefore, $N=2 \cdot 99^{2}: 2=99^{2}$.

On the other hand, $N$ must be even. Indeed, in each row and each column, the first and last cells are black; therefore, there must be an even number of color changes. Contradiction.