Loading [MathJax]/jax/output/SVG/jax.js

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


k2 натурал саны берілген. Келесі қасиетке ие барлық a1,a2, натурал сандарының барлық шексіз тізбегін табыңыз: теріс емес бүтін коэффициенттері c0,c1,,ck1 бар әрі барлық натурал n1 үшін P(an)=an+1an+2an+k болатындай P(x)=xk+ck1xk1++c1x+c0 түріндегі P көпмүшесі табылады.
посмотреть в олимпиаде

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

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

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

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

Пусть P=kj=1(an+j)=kj=1(an+g(j)))

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

P=akn+Ck1ak1n+...+C1an+kj=1g(j)=P(an)

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

an+g(j)=an+j=a1+f(n+j)

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

g(j)=a1+f(n+j)an=a1+f(n+j)a1f(n)

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

Это означает, что f(n) должна увеличиваться с ростом n или оставаться постоянной, а также с f(1)=0, потому что a1=a1+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)=mnm=(n1)м. Поскольку f(n) должно быть неотрицательным целым числом, тогда m0mZ, тогда f(n) является возрастающим или постоянным, причем f(1)=0

Тогда g(j)=f(n+j)f(n)=(n+j1)m(n1)m=jm

Это дает:

kj=1(an+jm)=P(an)=akn+Ck1ak1n+...+C1an+k!mk

с C0=k!mk и коэффициентами многочлена 0

Тогда an=a1+f(n)

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

an=a1+(n1)m, m0mZ и a11a1Z

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

P(x)=xk+ck1xk1++c1x+c0()

P(an)=an+1an+2an+k()

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

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

Возьмем минимальный элемент этой последовательности,  ai

Если i1 то:

P(ai)P(ai1) из ();   P(ai)P(ai1) из ()ai=ai1=ai+kai=K;iN

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

Если i12 все выходит также

Продолжая получаем что ak наименьший среди {ak,ak+1,,a}

a1<a2<<an1<an;nN 

Утерждение 2. i1=an+1anC; C  константа

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

C=ck1++c1+c0

an+1ak1n<P(an) из (); akn+Cak1nP(an) из ()  

Значения i1 может принимать конечное кол-во значений. Теперь если обозначить an+lan=il,1lk то для бесконечного кол-во an все il равны

Из этого для бесконечного кол-ва чисел P(an)=kl=1(an+il)

Используем факт того что P(x) имеет целые коэфиценты P(x)=kl=1(xn+il) для всех действительных x

Утверждение 3. il=li1

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

Индукция:

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

P(an+i1)=P(an+1)=an+2an+k+1=(an+i2)(an+ik)(an+ik+1)(an+il)P(an+i1) для бесконечного кол-во n

Поскольку P(x)  имеет целочисленные коэфиценты выходит что многочлен x+il нацело делится на P(x+i1)il=im+i1

При: ml2;  im+i1il1 из того что последовательность строго возрастающая: il>il1

При: ml;  im+i1>ilm=l1

Из этого можно получить что на самом деле: P(x)=kl=1(x+li1)

Утверждение 4. an+1an=i1;nN

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

an+2an+kan+k+1=P(an+1)=kl=1(an+1+li1)=an+2an+k(an+1+ki1)an+k+i1=an+k+1

an(an+i1)(an+(k1)i1)=P(an1)=(an1+i1)(an1+ki1)

Если взять an1<ani1 то левая часть будет больше, также при an1>ani1 правая часть окажется больше anan1=i1

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

Ответ: an=a1+(n1)i1 где iZ0

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

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

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

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

an+2an+kan+k+1=P(an+1)

P(an+1)=kl=1(an+1+li1)

kl=1(an+1+li1)=an+2an+k(an+1+ki1)

an+2an+k(an+1+ki1)=an+2an+kan+k+1an+1+ki1=an+k+1

an+(k+1)i1=an+k+i1=an+k+1

А по (3):

an+(k+1)i1=an+1+ki1==an+k+i1=an+k+1

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

an(an+i1)(an+(k1)i1)=P(an1)

P(an1)=(an1+i1)(an1+ki1)

an(an+i1)(an+(k1)i1)=(an1+i1)(an1+ki1)

Если anan1>i1 то:

an>an1+i1,an+i1>an1+2i1,,an+(k1)i1>an1+ki1 Т.к. тогда:

an(an+i1)(an+(k1)i1)>(an1+i1)(an1+ki1)

А если anan1<i1:

an<an1+i1,an+i1<an1+2i1,,an+(k1)i1<an1+ki1

Т.к. тогда:

an(an+i1)(an+(k1)i1)<(an1+i1)(an1+ki1)

Из чего:

an1+(k+1)i1=an+ki1==an+k

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

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