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