Question

Вася выписывает в ряд различные натуральные числа и следит за тем, чтобы любые 9 вы- писанных чисел имели общий делитель, больший единицы, а никакие 10 выписанных чисел такого общего делителя не имели (пока чисел меньше 9, на них ограничений нет). Докажите, что в какой-то момент Вася не сможет выписать очередное число.

Answer 1

Предположим противное, то есть то, что Вася всегда сможет выписать очередное число. В силу попарного различия выписываемых чисел, их множество неограниченно.

Рассмотрим первые 9 чисел. Пусть у них есть общий делитель $d>1$. Заменим теперь последнее число (9-ое в последовательности) на 10-ое в последовательности. Чисел снова 9 и у них должен быть общий делитель $d'>1$. Если при этом $(d,d')>1$, то можно взять первые 10 чисел и у них окажется общий делитель $(d,d')>1$, противоречие. Значит, $d$ и $d'$ взаимно просты. Далее заменяем 10-ое число на 11-ое и так далее. Получаем бесконечное множество чисел, поскольку они попарно взаимно просты. Но все эти числа делят первые 8 чисел множества, у которых множество делителей, очевидно, ограничено. Противоречие. Следовательно, в какой-то момент Вася не сможет выписать очередное число.