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

Пусть $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$. ( А. Васильев )

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

Вычислив первые 4 элемента последовательности получим $a_1=1, a_2=4, a_3=13, a_4=40$

Что дает нам $a_n=\frac{3^n-1}{2}$. Докажем это утверждение используя индукцию

Для $n$ справедливо $s(a_n)=\frac{3^{2n}-1}{8}$

Обозначим $q_n \in S$ как результат $s(m)-s(a_{n-1})$, тогда $q_n=s(a_n)-s(a_{n-1})=3^{2(n-1)}$

$q_{n+1}=s(a_{n+1})-s(a_n)=\frac{(a_{n+1})^2+a_{n+1}}{2}-\frac{3^{2n}-1}{8} \Rightarrow$ $8q_{n+1}=4a_{n+1}^2+4a_{n+1}+1-3^{2n} \Rightarrow$

$8q_{n+1}=(2a_{n+1}+1)^2-3^{2n} \Rightarrow$ $3^{2n}=(2a_{n+1}+1)^2-8q_{n+1} $ $(1)$

т.к. обе стороны должны делиться на 3 без остатка, то получим что $2a_{n+1}+1 \equiv 0 \pmod {3}$ и $q_{n+1} \equiv 0 \pmod {3}$

Обозначим $a_{n+1}=3g_n+1$ и $q_{n+1}=(3h_n)^2$

Получим уравнение $3^{2n}=(6g_n+3)^2-8(3h_n)^2 \Rightarrow 3^{2n-2}=(2g_n+1)^2-8h_n^2 $ что эквивалентно уравнению $(1)$

После всех сокращений получим $1=(2g_1+1)^2-2(2h_1)^2 $. Это уравнение Пелля с наименьшим решением $2h_1=2$. Т.е. $h_n=3^{n-1}$

Подставим в уравнение $(1)$ получим

$(2a_{n+1}+1)^2-8 \cdot 3^{2n}=3^{2n} \Rightarrow (2a_{n+1}+1)^2-3^{2(n+1)}=0 \Rightarrow a_{n+1}=\frac{3^{n+1}-1}{2}$

Далее докажем что если $l$ делит $k$, то $a_k$ делится на ${a_i}$

Пусть $k=p \cdot l$, тогда $a_k=\dfrac{3^{pl}-1}{2}=\dfrac{(3^l-1)((3^l)^{p-1}+(3^l)^{p-2}+...+(3^l)^0)}{2} \Rightarrow \dfrac{a_k}{a_l}=(3^l)^{p-1}+(3^l)^{p-2}+...+(3^l)^0$

Для второй части пусть $l \nmid k$ тогда $k=pl+q$ где $0<q<l$

$(3^{pl+q}-1)=(3-1)(3^{pl+q-1} + 3^{pl+q-2} + ... + 3^{pl}) + (3-1)(3^{pl-1} + 3^{pl} + ...+1)=(3-1)(3^{pl+q-1} + 3^{pl+q-2} + ... + 3^{pl})+(3^{pl}-1)$

т.к. $pl$ и делится на $l$, то (3^{pl}-1)$ делится на $(3^l-1)$

Из первой части выводим $3^{pl+q-1} + 3^{pl+q-2} + ... + 3^{pl}=3^{pl}(3^{q-1} + 3^{q-2} + ... + 1)$

Т.к. $GCD(3^{pl}$, $(3^l-1))=1$, а $(3^{q-1} + 3^{q-2} + ... + 1) < (3^{l-1} + 3^{l-2} + ... + 1)$ то получаем противоречие. Значит $q=0 \Rightarrow k=pl$

Антон Николаевич -- легенда!!!