Областная олимпиада по математике, 2020 год, 11 класс

Пусть $P(x)$ — многочлен степени $n \le 10$ с целыми коэффициентами такой, что для каждого $k\in \{1,2,\ldots,10\}$ существует целое число $m,$ что $P(m)=k.$ Докажите, что если $|P(10)-P(0)|<10000,$ то для любого $k \in \{1,2,\ldots,10000\}$ существует целое число $m$ такое, что $P(m)=k.$

Комментарий/решение

На самом деле можно доказать, что для любого целого $k$ существует целое $m$, что $P(m) = k$.

Факт 1:

Eсли коэффиценты $P(x)$ целые, то $P(a) - P(b) \equiv 0$ (mod $a-b$).

(Этот факт часто используется когда коэффиценты многочлена целые)

Пусть $m_1, m_2, \dots, m_{10}$ такие целые числа, что $P(m_i) = i$ для каждого $1 \leq i \leq 10$.

Утверждение 1:

Числа $\left \{ m_i \right \}$ последовательные.

Доказательство:

$$1 = P(m_{i+1}) - P(m_{i}) \equiv 0 (mod \ m_{i+1} - m_i)$$

Поэтому $m_{i+1} = m_{i} \pm 1$

Если $m_2 = m_1 + 1$, то $m_3 = m_2 + 1, m_4 = m_3 + 1$ и т.д.

Если же $m_2 = m_1 - 1$, то $m_3 = m_2 - 1, m_4 = m_3 - 1$ и т.д.

Утверждение 2:

$P(x + 1) - P(x) = 1$, если $\left \{ m_i \right \}$ возрастающая.

$P(x-1) - P(x) = 1$, если $\left \{ m_i \right \}$ убывающая.

Доказательство:

Разберем только первый случай, потому что второй ему аналогичен.

1. Случай: Последовательность $\left \{ m_i \right \}$ возрастающая.

Рассмотрим многочлен $Q(x) = P(x+1) - P(x)$, тогда степень $Q$ не больше $n - 1 \leq 9$ и коэффиценты $Q$ целые.

Мы знаем, что $Q(m_i) = 1$ при всех $i = 1, 2, \dots, 9$, значит

$Q(x) = a(x - m_1) (x - m_1 - 1)...(x - m_1 - 8) + 1$ для какого-то целого числа $a$.

Тогда $$ |P(10) - P(0)| = |Q(9) + Q(8) + ... + Q(0)| = |\sum \limits_{i=0}^{9} a(i - m_1) (i - m_1 - 1)...(i - m_1 - 8) + 10| = |\sum \limits_{i=0}^{9} a(m_1 - i) (m_1 + 1 - i)...(m_1 + 8 - i) - 10|$$.

Обозначим $S = |\sum \limits_{i=0}^{9} (m_1 - i) (m_1 + 1 - i)...(m_1 + 8 - i)|$, тогда по условию $|aS-10| < 10000 \Leftrightarrow -10000 + 10<aS<10000 + 10$

Докажем, что при $a \neq 0$ это условие не выполняется.

Заметим, что если $m_1 \geq 10$, то каждое слагаемое в $S$ делится $9!$ и не равно нулю, поэтому $|aS| \geq |S| > 9! > 10010$

Аналогично, при $m_1 \leq -10$, каждое слагаемое в $S$ делится на $-9!$ и не равно 0, поэтому $|aS| \geq |S| > 9! > 10010$

Если же $ -10 < m_1 < 10$, то абсолютно все слагаемые будут либо не отрицательными, либо не положительными и среди них обязательно найдется хотя бы одно не равное нулю. Также все слагаемые делятся на $9!$, поэтому $|aS| \geq |S| > 9! > 10010$

Значит, при $a \neq 0$ мы получаем противоречие, тогда $a = 0$, а $P(x+1) - P(x) = 1 (*)$

Примечание: Из этого можно вывести, что $P$ - многочлен первой степени

Завершение:

Из (*) легко получить, что:

$P(m+k-1) = P(m) + k - 1 = k$ для любого целого $k$.