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. 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)$.

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.

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 Bezout for integer polynomials (see problem $\underline{35562}$ ). Therefore, all values $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 are 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

![](https://cdn.mathpix.com/cropped/2024_05_06_7e3e695203bdf41f05f0g-04.jpg?height=240&width=2041&top_left_y=143&top_left_x=0)

Author: Galatenko A.

A table of size $2017 \times 2017$ is filled with non-zero digits. Among the 4034 numbers, whose decimal representations coincide with the rows and columns of this table, read from left to right and top to bottom respectively, all but one are divisible by a prime number $p$, while the remaining number is not divisible by $p$. Find all possible values of $p$.

## Solution

Number the rows (from bottom to top) and columns (from right to left) with numbers from 0 to 2016, and let $a_{i, j}$ denote the digit at the intersection of the $i$-th row and the $j$-th column. With this numbering, the digits

of the numbers being considered, which are in the least significant positions, have a smaller row (column) number.

If $v_{i}$ denotes the number written by the digits of the $i$-th row, and $w_{j}$ denotes the number written by the digits of the $j$-th column, then $v_{i}=\sum_{j=0}^{2016} 10^{j} a_{i, j}, \quad w_{j}=\sum_{i=0}^{2016} 10^{i} a_{i, j}$.

We will show that the situation described in the problem is possible for $p=2$ and $p=5$. For example, let $a_{i, j}=1$ for all $i, j \geq 1$ (these digits can be chosen as any others), $a_{0,2016}=1$, and the remaining digits are equal to $p$. Then all numbers read by rows and columns, except $w_{2016}$, end in $p$ and, as a result, are divisible by $p$, while $w_{2016}$ ends in 1 and therefore is not divisible by $p$.

Now we will prove that for other $p$ the described situation is impossible. Assuming the contrary, consider the quantity $S=\sum_{i, j=0}^{2016} 10^{i+j} a_{i, j}=\sum_{i=0}^{2016} 10^{i} \sum_{j=0}^{2016} 10^{j} a_{i, j}=\sum_{i=0}^{2016} v_{i}$

Similarly,

$$
S=\sum_{j=0}^{2016} w_{j}
$$

If all numbers $v_{i}, w_{j}(i, j=0,1,2, \ldots, 2016)$, except one, are divisible by $p$, and the remaining one is not divisible by $p$, then in one of the two last sums all terms are divisible by $p$ (which means $S$ is divisible by $p$), and in the other sum all terms, except one, are divisible by $p$, while the remaining one, due to the coprimality of $p$ and powers of ten, is not divisible by $p$. Contradiction.

## Answer

2 and 5.