Решение задачи 430

Условие:

Аня Валиуллина задумала число. Каждую минуту она прибавляет к текущему числу его наибольший собственный делитель. Через 100 минут она получила число 56789. Докажите, что Аня ошиблась. (Делитель числа n называется собственным, если он отличен от n).

Решение:

Операцией над числом n назовем прибавление к нему его наибольшего собственного делителя.

Рассмотрим четное число 2n. Его наибольший собственный делитель это n. Поэтому число 2n после операции превратится в число 3n, то есть увеличится в 3/2 раза.

Четное число 2n после операции могло превратиться в нечетное число 3n. Но из вышесказанного следует, что полученное число делится на 3. И тогда его наибольший собственный делитель это n. И после операции над числом 3n мы получим число 4n, то есть домножим его на 4/3.

Заметим, что любое нечетное число после операции становится четным, потому что у нечетного числа все делители нечетные, а сумма двух нечетных чисел четна.

Из всего вышесказанного следует, что начиная с третьего числа, оно будет получено путем умножения предыдущего на 3/2 или 4/3.

Получается, в конце какое-то натуральное число m умножили на 3/2 или 4/3 и получилось 456789. Осталось заметить, что 56789 не делится ни на 3, ни на 4, поэтому такое невозможно.