ЗАДАЧИ
problems.ru
О проекте | Об авторах | Справочник
Каталог по темам | по источникам |
К задаче N

Проект МЦНМО
при участии
школы 57
Задача 109872
Темы:    [ Основная теорема арифметики. Разложение на простые сомножители ]
[ Четность и нечетность ]
[ Доказательство от противного ]
Сложность: 3+
Классы: 7,8,9
В корзину
Прислать комментарий

Условие

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


Решение

Допустим, что нашлись числа a1, a2, ..., a1995, которые можно расставить требуемым образом. Пусть число ak  (k = 1, 2, ..., 1995)  представляется в виде произведения nk простых сомножителей (не обязательно различных). Так как каждые два соседние числа отличаются друг от друга одним простым множителем, то для каждого  k = 1, 2, ..., 1994  числа nk и nk+1 отличаются на единицу, то есть имеют разную чётность. Значит, числа n1, n3, ..., n1995 должны быть одной чётности. С другой стороны, числа a1995 и a1 также соседние, поэтому n1995 и n1 должны иметь разную чётность. Противоречие.


Ответ

Нельзя.

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

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

© 2004-... МЦНМО (о копирайте)
Пишите нам

Проект осуществляется при поддержке Департамента образования г.Москвы и ФЦП "Кадры" .