Областная олимпиада по математике, 2025 год, 10 класс

Пусть $s(n)=1+2+\ldots+n$, а $S=\{1,4,9,16,\ldots \}$ есть множество всех квадратов натуральных чисел. Определим последовательность таким образом, что $a_1=1$ и $a_{n+1}=\min \{m:(s(m)-s(a_n ))\in S\}$ для всех натуральных $n$. Докажите, что $a_k$ делится на $a_l$ тогда, и только тогда, когда $k$ делится на $l$. ( А. Васильев )

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

Ну сначала покажем что $a_n=\dfrac{3^n-1}{2}$

Заметим что надо доказать что:

min$(k)=3^n$ где$( \dfrac{3^n-1}{2}+1)+(\dfrac{3^n-1}{2}+2)+…+(\dfrac{3^n-1}{2}+k)=x^2$

Используя то что $1+3+…+(2n-1)=n^2$ можно преобразовать в:

$k \cdot 3^n+k^2=2x^2$ теперь если $x$ не делится на $3$ тогда мо моду 3 выходит что $k^2 \equiv 2 \pmod 3$ что невозможно и можно еще раз преобразовать в $k_1 \cdot 3^{n-1}+{k_1}^2=2{x_1}^2$. И так можно спускаться пока не останется $k_n+{k_n}^2=2{x_n}^2$ где $k_n \cdot 3^n=k$. Очевидно что минимальный $k_n$ который этому удовлетворяет это $k_n=1$ отсюда $k=3^n$.

Осталось понять что если $a_l | a_k$ тогда $3^l-1 | 3^k-1$ и это верно только тогда когда $l | k$.