Processing math: 0%

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


k натурал саны берілген. Келесі қасиетке ие барлық a_1, a_2, \ldots натурал сандарының барлық шексіз тізбегін табыңыз: теріс емес бүтін коэффициенттері c_0, c_1, \ldots, c_{k-1} бар әрі барлық натурал n \geq 1 үшін P\left(a_n\right)=a_{ n+1} a_{ n+2} \cdots a_{n+k} болатындай P(x)=x^k+c_{k-1} x^{k-1}+\cdots+c_1 x+c_0 түріндегі P көпмүшесі табылады.
посмотреть в олимпиаде

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

  4
1 года 5 месяца назад #

Пусть 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}

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

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 }

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

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

  1
1 года 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}

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

пред. Правка 2   6
11 месяца 24 дней назад #