Задача 109872

Темы:    [ Основная теорема арифметики. Разложение на простые сомножители ] [ Четность и нечетность ] [ Доказательство от противного ]

Сложность: 3+ Классы: 7,8,9

Условие

Автор: Шаповалов А.В.

Можно ли расставить по кругу 1995 различных натуральных чисел так, чтобы для каждых двух соседних чисел отношение большего из них к меньшему было простым числом?

Решение

Допустим, что нашлись числа a₁, a₂, ..., a₁₉₉₅, которые можно расставить требуемым образом. Пусть число a_k  (k = 1, 2, ..., 1995)  представляется в виде произведения n_k простых сомножителей (не обязательно различных). Так как каждые два соседние числа отличаются друг от друга одним простым множителем, то для каждого  k = 1, 2, ..., 1994  числа n_k и n_k+1 отличаются на единицу, то есть имеют разную чётность. Значит, числа n₁, n₃, ..., n₁₉₉₅ должны быть одной чётности. С другой стороны, числа a₁₉₉₅ и a₁ также соседние, поэтому n₁₉₉₅ и n₁ должны иметь разную чётность. Противоречие.

Ответ

Нельзя.

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

олимпиада
Название	Всероссийская олимпиада по математике
год
Год	1995
Этап
Вариант	4
Класс
Класс	9
задача
Номер	95.4.9.2