Международная олимпиада 2023, Чиба, Япония, 2023 год
Комментарий/решение:
Пусть 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}
По аналогии все предыдущие элементы будут равны
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.