Processing math: 27%

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


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

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

пред. Правка 3   3
2 года 11 месяца назад #

Ответ: P(x)x+b или P(x)xb для всех целых b2022.

Рассмотрим случай degP2. Пусть P(x)=adxd++a0. Замена PP ничего не меняет, поэтому БОО старший коэф. P больше нуля. Ясно, что degP1 и его старший коэф. равен dad.

Поэтому: (1) Сущ. MN, что P(x)>0,xM;

(2) Сущ. s,tN, что P(s)=t, а так же t2>(M+2022)t+sP(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 находим второй ответ.

  3
1 года 11 месяца назад #

Сперва поймем, что 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}.