Азиатско-Тихоокеанская математическая олимпиада, 2021 год

Для многочлена $P$ и натурального числа $n$ обозначим через $P_n$ количество пар натуральных чисел $(a, b)$ таких, что $a < b\leq n$ и $|P(a)|-|P(b)|$ делится на $n$. Найдите все многочлены $P$ с целыми коэффициентами такие, что $P_n\leq 2021$ для всех натуральных $n$.

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

Ответ: $P(x)\equiv x+b$ или $P(x)\equiv-x-b$ для всех целых $b\ge -2022.$

Рассмотрим случай $\deg P\ge 2.$ Пусть $P(x)=a_dx^d+\ldots+a_0.$ Замена $P\to -P$ ничего не меняет, поэтому БОО старший коэф. $P$ больше нуля. Ясно, что $\deg P'\ge 1$ и его старший коэф. равен $da_d.$

Поэтому: (1) Сущ. $M\in\mathbb N,$ что $P(x)>0,\forall x\ge M;$

(2) Сущ. $s,t\in\mathbb N,$ что $P'(s)=t,$ а так же $t^2>(M+2022)t+s\iff P'(s)^2-(M+2022)P'(s)-s>0.$

Лемма: Для $\forall x\equiv y\equiv s\pmod{t}$ верно, что $t^2\mid P(x)-P(y).$

Д-во: Можем записать так: $P(x)-P(y)=(x-y)Q(x,y).$ Заметим, что

$$Q(x,y)\equiv Q(x,x)\equiv P'(x)\equiv P'(s)\equiv 0\pmod t.\quad\blacksquare$$

Рассмотрим пары $(x,y)$ вида $(it+s,(i+1)t+s),$ где $i=M,\ldots,M+2021,$ тогда

$$t^2\mid P(x)-P(y)=|P(x)|-|P(y)|.$$

Следовательно для $n=t^2$ условие $P_n\le 2021$ не выполняется. Значит $\deg P=1$ (очевидно, что степень не 0).

Пусть $P(x)=ax+b.$ Замена $P\to -P$ ничего не меняет, поэтому достаточно решить случай $a>0.$ Сущ. $N\in\mathbb N,$ что $P(x)>0,\forall x\ge N.$

Если $a>1,$ то

$$a(x-y)=P(x)-P(y)=|P(x)|-|P(y)|,\forall x,y\ge N.$$

Пусть $m$ натуральное число такое, что $am>N+2021+m$. Рассмотрим пары $(x,y)$ вида $(N+i,N+i+m),$ где $i=0,\ldots, 2021$ тогда

$$am\mid (-am)=|P(x)|-|P(y)|,$$

следовательно для $n=am$ условие $P_n\le 2021$ не выполняется. Значит $P(x)=x+b.$ Если $b\le -2023,$ то для $n=2022-b\implies P_n=2022,$ что не удовлетворяет условию. Значит $b\ge -2022,$ что очевидно подходит. Обратной заменой $P\to -P$ находим второй ответ.

Сперва поймем, что $P$ не константа и БОО старший коэффициент положительный.

Существует $x_0$ такой, что $\forall x>x_0$ $P(x)$ положительный, поэтому наше условие можно заменить на такое: количество пар $(a, b)$ с $x_0 < a<b \leq n, P(a)-P(b) \vdots n$ ограничено.

Пусть $p$ простое и $p^2 | n$. По ряду Тейлора $\forall a, x_0 < a \leq n-\frac{n}{p}$,

$$P(x+\frac{n}{p})-P(x)=\frac{P'(x)}{1!} \cdot \frac{n}{p}+\frac{P''(x)}{2!} \cdot \left( \frac{n}{p} \right) ^2+\frac{P'''(x)}{3!} \cdot \left( \frac{n}{p} \right) ^3 +\cdots$$

Заметим, что при $p | P'(x)$ пара $(x+\frac{n}{p}, x)$ подходит: каждый член справа делится на $n$, потому что $\frac{P^{(d)}(x)}{d!} \in \mathbb{Z}$ и $n | \left( \dfrac{n}{p} \right)^2$. Из этого следует, что $p | P'(x)$ для ограниченного количества $x$. Вспомним, что $P'(x)$ - многочлен с целыми коэффициентами, значит $p | P'(x) \Leftrightarrow p | P'(x + pk) \forall k \in \mathbb{Z}$, значит если есть хотя бы для одного $x$ $P'(x) \vdots p$, то существует хотя бы $\frac{n}{p}-1-\left[ \frac{x_0-1}{p} \right]$ таких $x$ между $x_0$ и $n-\frac{n}{p}$. Но это число мы можем сделать произвольно большим, противоречие.

Тогда мы получили, что для всех больших $x$ $P'(x)$ не делится ни на какие простые $p$, то есть $|P'(x)| \leq 1$, значит это всегда $1$ и $P(x)=x+c$. Проверяем и получаем, что $\boxed{P(x)=\pm(x+c) \forall c \geq -2022}$.