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

Найдите все многочлены $P(x)$ с целыми коэффициентами, удовлетворяющие следующему условию:
Для любой бесконечной последовательности $a_1 ,a_2 , \ldots $ целых чисел, в которой каждое целое число встречается ровно один раз, существуют индексы $i < j$ и целое число $k$ такие, что выполнено равенство $a_i +a_{i+1} +\ldots +a_j = P(k)$.

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

Решение:

Д-ем, что многочлен $P$ степени 1 подходит. Пусть $P(x)=ax+b,$ и без ог. общности $a>b\ge 0.$ Пусть $s_i=a_1+\ldots+a_i,\forall i.$ Достаточно показать, что найдутся индексы $i-j\ge 2,$ что $s_i-s_j\equiv b\pmod a.$

Давайте рассмотрим индексы $k_0,\ldots,k_a>1$ для которых $a_{k_i}\equiv b\pmod a,\forall i.$

Тогда из Принципа Дирихле среди пар $(s_{k_i-1},s_{k_i})$ для $i=0,\ldots, a,$ найдутся индексы $m>n,$ что пары $(s_m,s_{m-1})$ и $(s_n,s_{n-1})$ будут равны по модулю $a,$ то есть

$$s_m-s_{n-1}\equiv s_{m}-(s_n-b)\equiv b\pmod a. $$

Д-ем, что многочлен $P$ степени не равной 1 не подходит.

Лемма: Если $\deg P\neq 1,$ то $\forall A,B,C\in \mathbb N,$ найдется целое $y,$ что $|y|>C$ и при этом никакое значение $P$ не лежит на отрезке $[y-A,y+B].$

Д-во леммы. Для четных степеней $P$ будет ограничена с одной из сторон откуда сразу следует требуемое.

Теперь рассмотрим $P(x)=a_nx^n+\ldots,$ где $n>1$ нечетное число. Можем считать, что $a_n>0,$ поскольку области значении $P(\mathbb Z)=P(-\mathbb Z).$

Заметим, что $P(x+1)-P(x)=na_nx^{n-1}+\ldots$ имеет положительный старший коэффициент и степень $>0.$ Тогда промежуток между $P(x)$ и $P(x+1)$ становится произвольно большим для больших $x,$ отсюда следует утверждение леммы.$\blacksquare$

Теперь будем индуктивно строить последовательность $\{a_i\}_{i\ge 1}$ из всех целых чисел, чтобы при этом для любых индексов $i<j$ и целого $k$

$$a_i+\ldots+a_j\neq P(k).$$

Допустим нам удалось построить первые $i$ элементов последовательности. Допустим $m$ наименьшее по модулю число, которого еще не было (если таких два, выберем любое).

Добавим еще два элемента. Возьмем $a_{i+2}=m.$ Рассмотрим все новые суммы хотя бы из двух последовательных элементов. Заметим, что каждое из них содержит $a_{i+1}.$ Понятно, что все они лежат на некотором отрезке $[a_{i+1}-A,a_{i+1}+B],$ для фиксированных натуральных $A,B.$ По лемме можно выбрать достаточно большое $a_{i+1},$ чтобы этот отрезок не содержал значений $P.$ $\square$

разве в вашем примере будет выполняться что каждое целое встречается ровно один раз?

Мы добавляем наименьшее по модулю число $m$, которого еще не было в последовательности, на место $a_{i+2},$ а $a_i$ выбирается так, что его нет среди остальных элементов последовательности (это так поскольку оно может быть сколь угодно большим).

По построению понятно, что таким образом все целые числа будут встречаться по одному разу.