Решение задачи 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, поэтому такое невозможно.