XIV математическая олимпиада «Шелковый путь», 2020 год

Дана строго возрастающая бесконечная последовательность натуральных чисел $a_1,$ $a_2,$ $a_3,$ $\ldots$. Известно, что $a_n \leq n+2020$ и число $n^3 a_n - 1$ делится на $a_{n+1}$ при всех натуральных $n$. Докажите, что $a_n = n$ при всех натуральных $n$. ( Сатылханов К. )

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

Комментарии от администратора Комментарии от администратора №1.     Пусть $b_n = a_n - n$ для всех $n$. Индукцией по $n$ легко показать, что $b_n \geq 0$ для любого $n$. Если $b_k > b_{k+1}$ для какого-то $k$, то $$a_k - k > a_{k+1} - k - 1 \implies a_k + 1 > a_{k+1} \implies a_k \geq a_{k+1}$$ --- противоречие. Следовательно, последовательность $\{b_n\}$ неубывает. С другой стороны, она ограничена сверху: $b_n = a_n - n \leq 2020$. Следовательно, существует такое неотрицательное целое $k$ и натуральное $t$, что $b_n = k$ для всех $n \geq t$. Значит, для всех $n \geq t$ $$a_{n+1} \ | \ n^3 a_n - 1 \implies n + k + 1 \ | \ n^3 (n + k) - 1 \implies$$ $$\implies n + k + 1 \ | \ n^3 (n + k) - 1 - (n + k + 1)(n^3 - n^2 + n(k+1) - (k+1)^2) = (k + 1)^3 - 1 \implies$$ $$\implies n + k + 1 \ | \ (k + 1)^3 - 1.$$ Но это возможно только если $k = 0$. Следовательно, $b_n = 0$ для всех достаточно больших $n$, а значит и для всех $n$, т. е. $a_n = n$ для всех $n$.

Заметим, что $a_{n+1}\ge a_{n}+1\implies a_{n}\ge n, \forall n.$ Допустим $a_i>i$ для некоторого $i\implies a_n>n,\forall n\ge i.$

Из условия следует, что $\gcd (a_{n+1},n)=1.$ Выберем $n>i,$ что $2021!\mid n,$ тогда

$$1=\gcd (a_{n+1},n)=\gcd (a_{n+1}-n,n)=a_{n+1}-n>1,$$

противоречие. Последнее равенство следует из неравенства $1<a_{n+1}-n\le 2021.$

$\mathbf{Statement:}$

Если существует какой-то $a_i$ для которого $a_i \geq i+j$ то и существует какой-то $a_s$ что $a_s \geq s+j+1$.

$\mathbf{Proof:}$

Давайте рассмотрим любой $w\geq i$, то для него будет что $a_w \geq w+j$, теперь подберем $w$ такой что бы $(j+1)|w$ и рассмотрим тот факт что $a_{w+1}|w^3a_w-1$, а еще мы знаем что $a_{w+1}\geq w+j+1$, рассмотрим два случая...

Первый, $a_{w+1}=w+j+1$, а он делится на $j+1$, значит и $w^3a_w-1$ делится на $j+1$, что невозможно ибо $w$ делится на $j+1$, соответственно этот случай невозможен.

Второй, $a_{w+1}\geq w+j+2$, значит мы доказали наше утверждение.

$\mathbf{Conclusion:}$

Получается, каждый раз мы будем находить какое-то $a_n \geq n+s$ где каждый раз $s$ будет увеличиваться при каких-то больших $n$, что даст противоречие по пункту того что $a_n\leq n+2020$.