Задача 67291

Темы:    [ Последовательности (прочее) ] [ Основная теорема арифметики. Разложение на простые сомножители ]

Сложность: 4 Классы: 8,9,10,11

Условие

Автор: Кожевников П.А.

Возрастающая последовательность натуральных чисел $a_1 < a_2 < \dots$ такова, что при каждом целом $n > 100$ число $a_n$ равно наименьшему натуральному числу, большему чем $a_{n-1}$ и не делящемуся ни на одно из чисел $a_1, a_2, \dots, a_{n-1}$. Докажите, что в такой последовательности лишь конечное количество составных чисел.

Решение 1

Пусть последовательность $S$ из условия задачи содержит бесконечно много составных чисел. Так как члены с номерами больше 100 не делятся на другие члены последовательности, она не содержит 1.

Пусть $p_1,p_2,\dots, p_k$ – все простые числа, не превосходящие $a_{100}$. Все остальные простые числа входят в $S$: действительно, пусть $q$ – одно из них, и пусть $a_t$ – наибольшее число в последовательности, меньшее чем $q$. Тогда $q$ больше $a_1,\dots, a_t$ и не делится на них (так как единицы среди них нет), причём меньшего числа с такими свойствами не существует. Следовательно, $a_{t+1}=q$.

Никакой другой член исходной последовательности не делится на $q$: предыдущие меньше $q$, а последующие не делятся на члены с меньшими номерами. Следовательно, составные числа из $S$ не имеют простых делителей кроме $p_1,\dots, p_k$.

Дальше возможны два способа решения.

Первый способ. Пусть $1\le i\le k$, и пусть $r=p_i^{d_i}$ – наименьшая степень числа $p_i$, которая больше $a_{100}$. Если $S$ не содержит меньшей степени $p_i$, то $r$ не делится на меньшие числа из $S$ и потому содержится в $S$. Таким образом, для каждого из чисел $p_1,\dots,p_k$ некоторая его степень содержится в $S$. Пусть $P$ – произведение всех этих степеней. Если в $S$ есть составное число $m$, большее чем $a_{100}$, то оно не делится на эти степени и на остальные простые числа, поэтому $m\le P$.

Второй способ. Пусть $S_0$ – совокупность всех составных чисел из $S$, имеющих номера больше 100. Предположим, что $S_0$ бесконечно. Пусть $m_1$ – наименьшее число из $S_0$. Любое другое число из $S_0$ не делится на $m_1$, поэтому какое-то $p_i$, где $1\le i\le k$, входит в его разложение с меньшим показателем, чем в разложение $m_1$. Для некоторого $i$ количество таких чисел бесконечно, а среди них бесконечно много таких, что в их разложении показатель при $p_i$ одинаков. Совокупность таких чисел обозначим $S_1$.

Дальше рассуждаем аналогично: пусть $m_2$ – наименьшее число из $S_1$, тогда любое другое число из $S_1$ не делится на $m_2$, и т.д. Получаем бесконечное множество чисел из $S_1$, в разложении которых одинаков показатель при некотором $p_j$ ($j\ne i,\ 1\le j\le k$). Это бесконечное множество обозначим $S_2$, и т.д.

В итоге получаем бесконечное множество $S_{k-1}$ членов исходной последовательности, у которых номера больше 100, а разложения отличаются показателем лишь при одном простом множителе. Но если $n_1,n_2$ – два числа из $S_{k-1}$ и этот показатель больше у $n_1$, то $n_1$ делится на $n_2$ и они не могут одновременно принадлежать исходной последовательности – противоречие. (В действительности $S_k$ можно построить по тому же правилу, и получится бесконечное множество, в котором все числа на самом деле равны.)

Решение 2

Докажем, что все $a_m$, большие $(a_{100})^2$, – простые числа. Предположим противное, тогда некоторое $a_m > (a_{100})^2$ раскладывается как $a_m = dt$, где $1 < t\leq d < a_m$, и следовательно $a_{100} < d < a_m$. Согласно определению $a_m$, $d$ не является ни одним из $a_1, a_2, \ldots, a_{m-1}$. Тогда $a_k < d < a_{k+1}$ для какого-то $k\in \{100, 101, \ldots, m-1\}$. Раз $d$ не было выбрано в качестве $a_{k+1}$, оно делится на какое-то $a_i$, $i\in \{1, 2, \ldots, k\}$. Но тогда и $a_m$ делится на $a_i$. Противоречие.

Источники и прецеденты использования

олимпиада
Название	Турнир городов
год/номер
Номер	42
Дата	2020/21
тур
Вариант	устный тур
задача
Номер	4