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

Проект МЦНМО
при участии
школы 57
Задача 65743
Темы:    [ Количество и сумма делителей числа ]
[ НОД и НОК. Взаимная простота ]
[ Уравнения в целых числах ]
Сложность: 4-
Классы: 8,9,10
В корзину
Прислать комментарий

Условие

Саша выбрал натуральное число  N > 1  и выписал в строчку в порядке возрастания все его натуральные делители:  d1 < ... < ds  (так что  d1 = 1  и
ds = N).  Затем для каждой пары стоящих рядом чисел он вычислил их наибольший общий делитель; сумма полученных  s – 1  чисел оказалась равной
N – 2.  Какие значения могло принимать N?


Решение

  Заметим, что  ds+1–i = N/di  при всех  i = 1, 2, 3, ..., s.
  Число  di+1di  делится на  (di, di+1),  так что  (di, di+1) ≤ di+1di.  При  i = 1, 2, s – 1  обозначим  ri = (di+1di) – (di, di+1) ≥ 0.  По условию
(d2d1) + (d3d2) + ... + (ds – ds–1) = ds – d1 = N – 1,  а  (d1, d2) + (d2, d3) + ... + (ds–1, ds) = N – 2.
  Вычитая, получим  r1 + r2 + ... + rs–1 = 1.  Это означает, что  rk = 1  для некоторого k, а все остальные ri равны нулю.
  Левая часть равенства  (dk+1dk) – (dk, dk+1) = 1  делится на  (dk, dk+1),  поэтому  (dk, dk+1) = 1  и  dk+1dk = 2.  Это возможно, только если каждое из чисел dk и dk+1 нечётно.
  Так как dk и dk+1 – два последовательных делителя числа N, то N/dk+1 и N/dk – тоже два последовательных делителя числа N: если  N/dk+1 = dm,  то
N/dk = dm+1.  При этом  (dm, dm+1) = N/[dk,dk+1] = N(dk,dk+1)/dkdk+1 < N(dk+1dk)/dkdk+1 = dm+1dm.
  Значит,  rm > 0,  что возможно лишь при  k = m  (и, следовательно,  s = 2k).
  Итак,  dk+1 = N/dk,  то есть число  N = dkdk+1  нечётно. Но тогда  ds–1N/3,  откуда  (ds–1, ds) ≤ ds–1N/3.  Следовательно,  1 ≥ rs–12N/3N/3 = N/3,  то есть  N ≤ 3.  Поскольку  N > 1,  получаем единственно возможное значение  N = 3,  которое, как легко убедиться, удовлетворяет условию.


Ответ

N = 3.

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

олимпиада
Название Всероссийская олимпиада по математике
год
Вариант 2015/2016
этап
Вариант 5
класс
Класс 9
задача
Номер 9.3

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

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