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

Проект МЦНМО
при участии
школы 57
Задача 64632
Темы:    [ НОД и НОК. Взаимная простота ]
[ Четность и нечетность ]
[ Принцип крайнего (прочее) ]
Сложность: 4-
Классы: 10,11
В корзину
Прислать комментарий

Условие

По кругу стоят 101000 натуральных чисел. Между каждыми двумя соседними числами записали их наименьшее общее кратное.
Могут ли эти наименьшие общие кратные образовать 101000 последовательных чисел (расположенных в каком-то порядке)?


Решение

  Пусть  n = 101000.  Обозначим исходные числа (в порядке обхода) через  a1, ..., an; мы будем считать, что  an+1 = a1.  Положим  bi = НОК(ai, ai+1).  Предположим что  b1, ..., bn  – это n подряд идущих натуральных чисел.
  Рассмотрим наибольшую степень двойки 2m, на которую делится хотя бы одно из чисел ai. Заметим, что ни одно из чисел  b1, ..., bn не делится на 2m+1. Пусть для определённости a1 делится на 2m; тогда b1 и bn кратны 2m:  b1 = 2mxbn = 2my  при некоторых нечётных x и y. Без ограничения общности можно считать, что  x < y.  Тогда среди n последовательных чисел  b1, ..., bn  должно быть и число  2m(x + 1)  (поскольку  2mx < 2m(x + 1) < 2my).  Но это число делится на 2m+1 (так как  x + 1  чётно), что невозможно. Противоречие.


Ответ

Не могут.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Год 2013-2014
этап
1
Вариант 4
класс
Класс 10
задача
Номер 10.7

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

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