Международная олимпиада 2023, Чиба, Япония, 2023 год

Дано натуральное число $k \geqslant 2$. Найдите все бесконечные последовательности положительных целых чисел $a_1, a_2, \ldots$ со следующим свойством: существует многочлен $P$ вида $$P(x)=x^k+c_{k-1} x^{k-1}+\cdots+c_1 x+c_0$$ с неотрицательными целыми коэффициентами $c_0, c_1, \ldots, c_{k-1}$ такой, что $$P\left(a_n\right)=a_{n+1} a_{n+2} \cdots a_{n+k}$$ для всех натуральных $n \geq 1$.

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

Пусть $f(n)$ $g(j)$ будут функциями положительных чисел $n$ и $j$.

Пусть $a_n=a_n+1+f(n)$, Тогда $a_n+1=a_1+f(n+1)$ и этого $a_n+k=a_1+f(n+k)$

Пусть $P=\prod_{j=1}^{k}\left ( a_{n+j} \right ) = \prod_{j=1}^{k}\left ( a_{n}+g(j )) \right )$

Если мы хотим, чтобы коэффициенты при $P(a_{n})$ были положительными, то $g(j)\geq 0$ для всех $j$, что даст следующее значение для $P$:

$P=a_{n}^{k}+C_{k-1}a_{n}^{k-1}+...+C_{1}a_{n}+\prod_{j=1}^ {k} g(j) = P(a_{n})$

Таким образом, для каждых $j$ и $n$ нам нужно следующее:

$a_{n}+g(j)=a_{n+j}=a_{1}+f(n+j)$

Решая уравнение $g(j)$, получаем:

$g(j)=a_{1}+f(n+j)-a_{n}=a_{1}+f(n+j)-a_{1}-f(n)$

$g(j)=f(n+j)-f(n)\geq 0$ для всех $n$ и $j$, потому что $g(j)$ должен быть больше или равен нулю, чтобы все коэффициенты соответствовали быть неотрицательным.

Это означает, что $f(n)$ должна увеличиваться с ростом $n$ или оставаться постоянной, а также с $f(1)=0$, потому что $a_{1}=a_{1}+f(1)$ .

Кроме того, поскольку нам нужно, чтобы все коэффициенты были целыми, то и все $f(n)$ и $g(j)$ также должны быть целыми. Нам также необходимо, чтобы $g(j)$ не зависел от $n$, поэтому в выражении $f(n+j)-f(n)$ $n$ необходимо сократить. Это означает, что скорость изменения $f(n)$ по отношению к $n$ должна быть постоянной. Этого можно достичь только если $f(n)$ — уравнение линии с наклоном, равным нулю или положительному целому числу.

Итак, мы полагаем, что $f(n)$ — это уравнение прямой как $f(n)=mn+b$, где $m$ — это наклон с неотрицательным значением, а $b$ — точка пересечения в точке $. n=0$. Мы знаем, что $f(1)=0$, поэтому $f(1)=m+b=0$, что означает, что $b=-m$ и наша функция становится $f(n)=mn-m=(n- 1)м$. Поскольку $f(n)$ должно быть неотрицательным целым числом, тогда $m\geq 0 \mid m \in \mathbb{Z}$, тогда $f(n)$ является возрастающим или постоянным, причем $f(1)= 0$

Тогда $g(j)=f(n+j)-f(n)=(n+j-1)m-(n-1)m=jm$

Это дает:

$\prod_{j=1}^{k}\left ( a_{n}+jm \right )=P(a_{n})=a_{n}^{k}+C_{k-1}a_{ n}^{k-1}+...+C_{1}a_{n}+k!m^{k}$

с $C_{0}=k!m^{k}$ и коэффициентами многочлена $\geq 0$

Тогда $a_{n}=a_{1}+f(n)$

Что обеспечивает решение всех бесконечных последовательностей положительных целых чисел как:

$a_{n}=a_{1}+(n-1)m$, $\forall m\geq 0 \mid m \in \mathbb{Z}$ и $a_{1} \geq 1 \mid a_{ 1} \in \mathbb{Z}$

\[ P(x)=x^k+c_{k-1}x^{k-1}+\dots + c_1 x+c_0 (*)\]

\[ P(a_n)=a_{n+1}a_{n+2}\cdots a_{n+k}(**) \]

\[ \]

Утверждение 1. Последовательность является строго растущей либо константой$(K)$.

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

\[ \]

Возьмем минимальный элемент этой последовательности, $\text{ } a_i$

Если $i \ne 1$ то:

$P(a_i) \leq P(a_{i-1})$ из $(*);$ $\text{ } $ $P(a_i) \geq P(a_{i-1})$ из $(**) \Rightarrow a_i=a_{i-1}=a_{i+k} \Rightarrow a_i=K; i \in \mathbb{N}$

Теперь $i=1$. Аналогично возьмем второй наименьший элемент $a_{i_1}$

Если $i_1 \ne 2$ все выходит также

Продолжая получаем что $a_k$ наименьший среди $\{a_k, a_{k+1},\dots, a_\infty \}$

$a_1 < a_2 < \dots < a_{n-1} < a_n; n \in \mathbb{N} \text{ } \blacksquare$

$$$$

Утерждение 2. $i_1=a_{n+1}-a_n \leq C; \text{ } C \text{ } - $ константа

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

\[ \]

$C= c_{k-1}+\dots+c_1+c_0$

$a_{n+1}a_n^{k-1}<P(a_n)$ из $(**); \text{ } a_n^k+Ca_n^{k-1} \geq P(a_n)$ из $(*)$ $\text{ } \blacksquare$

Значения $i_1$ может принимать конечное кол-во значений. Теперь если обозначить $a_{n+l}-a_n=i_l, 1 \leq l \leq k$ то для бесконечного кол-во $a_n$ все $i_l$ равны

Из этого для бесконечного кол-ва чисел $P(a_n)=\prod \limits_{l=1}^{k}{(a_{n}+i_l)}$

Используем факт того что $P(x)$ имеет целые коэфиценты $\Rightarrow P(x)=\prod \limits_{l=1}^{k}{(x_{n}+i_l)}$ для всех действительных $x$

\[ \]

Утверждение 3. $i_l = li_1$

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

\[ \]

Индукция:

Проверим $l=1$ что очевидно работает. Допустим мы доказали это вплоть до $l-1;$

$P(a_n+i_1)=P(a_{n+1})=a_{n+2}\cdots a_{n+k+1}=(a_n+i_2)\cdots(a_n+i_k)(a_n+i_{k+1}) \Rightarrow (a_n+i_l) \mid P(a_n+i_1)$ для бесконечного кол-во $n$

Поскольку $P(x) \text{ } - $ имеет целочисленные коэфиценты выходит что многочлен $x+i_l$ нацело делится на $P(x+i_1) \Rightarrow i_l = i_m+i_1$

При: $m \leq l-2; \text{ }$ $i_m+i_1 \leq i_{l-1}$ из того что последовательность строго возрастающая: $i_l>i_{l-1}$

При: $m \geq l; \text{ }$ $ i_m+i_1 > i_l \Rightarrow m={l-1}$ $\blacksquare$

Из этого можно получить что на самом деле: $P(x)= \prod \limits_{l=1}^{k}{(x+li_1)}$

\[ \]

Утверждение 4. $a_{n+1}-a_n=i_1; n \in \mathbb{N}$

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

\[ \]

$ a_{n+2}\dots a_{n+k}a_{n+k+1}=P(a_{n+1})= \prod \limits_{l=1}^{k}{(a_{n+1}+li_1)}=a_{n+2}\dots a_{n+k}(a_{n+1}+ki_1) \rightarrow a_{n+k}+i_1=a_{n+k+1}$

$ a_n(a_n+i_1)\dots (a_n+(k-1)i_1)= P(a_{n-1})= (a_{n-1}+i_1)\dots (a_{n-1}+ ki_1)$

\[ \]

Если взять $a_{n-1} < a_n - i_1$ то левая часть будет больше, также при $a_{n-1} > a_n - i_1$ правая часть окажется больше $\rightarrow a_n-a_{n-1}=i_1 \blacksquare$

\[ \]

Теперь мы знаем что наша последовательность является арифметической прогрессией, из Утверждения 1. также выходит что она не убывает

\[ \]

Ответ: $ a_n = a_1+(n-1){i_1}$ где $i \in \mathbb{Z}_{ \geq 0 }$

Можете по подробнее доказать свое 4 утверждение тк мне кажется вы упустили какую та вещь

Окей, короче заметим:

$$a_{n+2}\dots a_{n+k}a_{n+k+1}=P(a_{n+1})$$

$$P(a_{n+1})= \prod \limits_{l=1}^{k}{(a_{n+1}+li_1)}$$

$$\prod \limits_{l=1}^{k}{(a_{n+1}+li_1)}=a_{n+2}\dots a_{n+k}(a_{n+1}+ki_1) $$

$$a_{n+2}\dots a_{n+k}(a_{n+1}+ki_1)=a_{n+2}\dots a_{n+k}a_{n+k+1}\rightarrow a_{n+1}+ki_1=a_{n+k+1} $$

$$a_n+(k+1)i_1=a_{n+k}+i_1=a_{n+k+1}$$

А по $(3):$

$$a_n+(k+1)i_1=a_{n+1}+ki_1=\dots = a_{n+k}+i_1= a_{n+k+1}$$

По аналогии все последующие элементы будут равны

\[ \]

$$a_n(a_n+i_1)\dots (a_n+(k-1)i_1)= P(a_{n-1})$$

$$P(a_{n-1})= (a_{n-1}+i_1)\dots (a_{n-1}+ ki_1)$$

$$a_n(a_n+i_1)\dots (a_n+(k-1)i_1)=(a_{n-1}+i_1)\dots (a_{n-1}+ ki_1)$$

Если $a_n - a_{n-1} > i_1$ то:

$$a_n > a_{n-1}+i_1, a_n + i_1 > a_{n-1} +2i_1, \dots, a_n+ (k-1)i_1 > a_{n-1}+ki_1 \Rightarrow \varnothing$$ Т.к. тогда:

$$a_n(a_n+i_1)\dots (a_n+(k-1)i_1)>(a_{n-1}+i_1)\dots (a_{n-1}+ ki_1)$$

А если $a_n - a_{n-1} < i_1:$

$$a_n < a_{n-1}+i_1, a_n + i_1 < a_{n-1} +2i_1, \dots, a_n+ (k-1)i_1 < a_{n-1}+ki_1 \Rightarrow \varnothing$$

Т.к. тогда:

$$a_n(a_n+i_1)\dots (a_n+(k-1)i_1)<(a_{n-1}+i_1)\dots (a_{n-1}+ ki_1)$$

Из чего:

$$a_{n-1}+(k+1)i_1=a_n+ki_1=\dots= a_{n+k}$$

По аналогии все предыдущие элементы будут равны