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

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

Условие

Изначально на доске написано натуральное число N. В любой момент Миша может выбрать число  a > 1  на доске, стереть его и дописать все натуральные делители a, кроме него самого (на доске могут появляться одинаковые числа). Через некоторое время оказалось, что на доске написано N² чисел. При каких N это могло случиться?


Решение

  Пусть  N > 1,  а  1 = d1 < d2 < ... < dk < dk+1 = N  – все делители числа N.
  Заметим, что  didk+2–i = N. Поэтому     < N2   (последнее неравенство следует из задачи 30898).
  Отсюда следует, что
  1) на первом шаге сумма квадратов написанных на доске чисел уменьшается;
  2) при следующих шагах она не увеличивается.
  Таким образом, сумма квадратов написанных на доске чисел во все моменты, кроме начального, меньше N². Поскольку все числа натуральные, их количество тоже меньше чем N².


Ответ

Только при  N = 1.

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

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

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

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