Международная олимпиада 2026, Шанхай, 2026 год

$a_1,a_2,a_3,\ldots$ тізбегі 1-ден үлкен бүтін сандардан тұратын шексіз тізбек болсын. Белгілі болғандай, әрбір оң бүтін $n$ үшін келесі шарт орындалады: барлық $i=1,2,\ldots,n$ үшін $\text{ЕҮОБ}(t,a_i) > 1 $ болатындай және $t > a_n$ болатын ең кіші бүтін сан $t$ дәл $a_{n+1}$-ге тең. Барлық оң бүтін $n$ үшін $$ a_{n+T}=a_n+L $$ теңдігі орындалатындай оң бүтін $T$ және $L$ сандары табылатынын дәлелдеңіз.

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

Достаточно доказать, что существуют подходящие $L$ и $T$. Это не сложно заметить, так как в последовательности встречаются только натуральные числа, упростив задачу с последовательности в которой встречаются действительные числа.

Зафиксируем простое число $p > a_1$. Рассмотрим подпоследовательность всех $a_i$ делящихся на $p$, и пусть $a_{i_n} = p^{k_n}c_n$, где $p \nmid c_n$.

Докажем, что для любого натурального $n$ в последовательности существует также член вида $q_n^{m_n} c_n < a_{i_n}$ для $m_n \geq 0$, где $q_n$ - простое, делящее $(c_n, a_1) = (a_{i_n}, a_1) > 1$, где последнее равенство верно так как $p \nmid a_1$. Докажем индукцией по $n$.

Для доказательства базы $n=1$, рассмотрим $m_1 \geq 0$ такое, что ${q_1}^{m_1+1} > p^{k_1} > {q_1}^{m_1}$, где неравенства строгие, потому что $p \neq q_n$. Рассмотрим $N_1 = {q_1}^{m_1} c_1 < p^{k_1} c_1 = a_{i_1}$, для которого также верно $N_1 \geq {q_1}^{m_1+1} > p^{k_1} \geq p > a_1$. То есть $a_{i_1} > N_1 > a_1$. Рассмотрим какой то $a_k < N_1 < a_{i_1}$ и простое $r$, делящее $(a_k, a_{i_1})>1$, тогда $r \mid c_n$, так как $r \neq p$, так как $a_{i_1}$ - первый член, делящийся на $p$. То есть $r \mid (a_k, N_1)$, то есть $(N_1, a_k) > 1$ для всех $a_k<N_1$. Очевидно, что $N_1$ обязан быть в последовательности. База доказана.

Рассмотрим $a_{i_n} = p^{k_n}c_n$ для произвольного $n \geq 2$ и предположим, что в последовательности встречаются $N_j = q_j^{m_j} c_j$ для $n > j \geq 1$. Как и в базе, выберем $m_n$, для которого ${q_n}^{m_n+1} > p^{k_n} > {q_n}^{m_n}$, где неравенства строгие по той же причине. Пусть $N_n = {q_n}^{m_n} c_n$. Аналогично $a_{i_n} > N_n > a_1$. Если $N_n$ не содержится в последовательности, то $(N_n, a_k) = 1$ для какого то натурального $k$. Если $p \nmid a_k$, то противоречие получается аналогично случаю в базе. Если $k = i_j$ для $j<n$. Рассмотрим простое $r$, делящее $(q_j^{m_j} c_j, a_{i_n})>1$. $p \nmid c_j$ и $q_j \mid c_j$, поэтому $r \neq p$ и $r \mid (c_j, c_n)$, поэтому $r \mid (N_n, a_k) = 1$. Противоречие завершает шаг.

Сопоставим каждому числу набор его простых $\leq a_1$. Если $a_n$ делится на простое $p>a_1$, мы можем выбрать меньший член такой, что его набор простых совпадает с $a_n$ по всем простым, кроме $p$. Убирая большие простые, мы придем к числу $s$ состоящему только из маленьких простых $a_n$. Очевидно, что любое число $t$ делящееся на все простые из этого набора будет содержаться в последовательности, так как оно не взаимнопросто ни с одним из чисел в последовательности (так как в ней есть число $s$ только из этих простых и любые два члена последовательности не взаимнопросты), в том числе всеми $a_k < t$.

Таких наборов конечное число и для каждого из них есть наименьшее число $\geq a_1$, содержащее этот набор, которое либо есть в последовательности, либо его нет, и в таком случае ни одно число не может содержать ровно этот набор. Значит мы можем выписать все наборы встречающиеся в этой последовательности. Любое число $\geq a_1$, делящееся хотя бы на один из этих наборов будет присутствовать, при этом чисел которые не делятся ни на один из них не будет, так как набор маленьких простых такого числа не выписан. Принадлежит число такой последовательности или нет определяется по модулю $P$, произведения всех простых $\leq a_1$. То есть мы можем взять $L = P$.