Международная олимпиада 2023, Чиба, Япония, 2023 год
Комментарий/решение:
Пусть 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+Ck−1ak−1n+...+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)−a1−f(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)=mn−m=(n−1)м. Поскольку f(n) должно быть неотрицательным целым числом, тогда m≥0∣m∈Z, тогда f(n) является возрастающим или постоянным, причем f(1)=0
Тогда g(j)=f(n+j)−f(n)=(n+j−1)m−(n−1)m=jm
Это дает:
∏kj=1(an+jm)=P(an)=akn+Ck−1ak−1n+...+C1an+k!mk
с C0=k!mk и коэффициентами многочлена ≥0
Тогда an=a1+f(n)
Что обеспечивает решение всех бесконечных последовательностей положительных целых чисел как:
an=a1+(n−1)m, ∀m≥0∣m∈Z и a1≥1∣a1∈Z
P(x)=xk+ck−1xk−1+⋯+c1x+c0(∗)
P(an)=an+1an+2⋯an+k(∗∗)
Утверждение 1. Последовательность является строго растущей либо константой(K).
Доказательство:
Возьмем минимальный элемент этой последовательности, ai
Если i≠1 то:
P(ai)≤P(ai−1) из (∗); P(ai)≥P(ai−1) из (∗∗)⇒ai=ai−1=ai+k⇒ai=K;i∈N
Теперь i=1. Аналогично возьмем второй наименьший элемент ai1
Если i1≠2 все выходит также
Продолжая получаем что ak наименьший среди {ak,ak+1,…,a∞}
a1<a2<⋯<an−1<an;n∈N ◼
Утерждение 2. i1=an+1−an≤C; C − константа
Доказательство:
C=ck−1+⋯+c1+c0
an+1ak−1n<P(an) из (∗∗); akn+Cak−1n≥P(an) из (∗) ◼
Значения i1 может принимать конечное кол-во значений. Теперь если обозначить an+l−an=il,1≤l≤k то для бесконечного кол-во an все il равны
Из этого для бесконечного кол-ва чисел P(an)=k∏l=1(an+il)
Используем факт того что P(x) имеет целые коэфиценты ⇒P(x)=k∏l=1(xn+il) для всех действительных x
Утверждение 3. il=li1
Доказательво:
Индукция:
Проверим l=1 что очевидно работает. Допустим мы доказали это вплоть до l−1;
P(an+i1)=P(an+1)=an+2⋯an+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
При: m≤l−2; im+i1≤il−1 из того что последовательность строго возрастающая: il>il−1
При: m≥l; im+i1>il⇒m=l−1 ◼
Из этого можно получить что на самом деле: P(x)=k∏l=1(x+li1)
Утверждение 4. an+1−an=i1;n∈N
Доказательство:
an+2…an+kan+k+1=P(an+1)=k∏l=1(an+1+li1)=an+2…an+k(an+1+ki1)→an+k+i1=an+k+1
an(an+i1)…(an+(k−1)i1)=P(an−1)=(an−1+i1)…(an−1+ki1)
Если взять an−1<an−i1 то левая часть будет больше, также при an−1>an−i1 правая часть окажется больше →an−an−1=i1◼
Теперь мы знаем что наша последовательность является арифметической прогрессией, из Утверждения 1. также выходит что она не убывает
Ответ: an=a1+(n−1)i1 где i∈Z≥0
Можете по подробнее доказать свое 4 утверждение тк мне кажется вы упустили какую та вещь
Окей, короче заметим:
an+2…an+kan+k+1=P(an+1)
P(an+1)=k∏l=1(an+1+li1)
k∏l=1(an+1+li1)=an+2…an+k(an+1+ki1)
an+2…an+k(an+1+ki1)=an+2…an+kan+k+1→an+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+(k−1)i1)=P(an−1)
P(an−1)=(an−1+i1)…(an−1+ki1)
an(an+i1)…(an+(k−1)i1)=(an−1+i1)…(an−1+ki1)
Если an−an−1>i1 то:
an>an−1+i1,an+i1>an−1+2i1,…,an+(k−1)i1>an−1+ki1⇒∅ Т.к. тогда:
an(an+i1)…(an+(k−1)i1)>(an−1+i1)…(an−1+ki1)
А если an−an−1<i1:
an<an−1+i1,an+i1<an−1+2i1,…,an+(k−1)i1<an−1+ki1⇒∅
Т.к. тогда:
an(an+i1)…(an+(k−1)i1)<(an−1+i1)…(an−1+ki1)
Из чего:
an−1+(k+1)i1=an+ki1=⋯=an+k
По аналогии все предыдущие элементы будут равны
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.