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

Условие:

На экране компьютера написано число 1. Каждую секунду компьютер прибавляет к числу, написанному на экране, его сумму цифр. Может ли через какое-то время на экране оказаться число 1234567890987654321?

Решение:

Будем пользоваться тем, что любое натуральное число имеет тот же остаток при делении на 3, что и его сумма цифр. Пусть какое-то число имеет остаток 1 при делении на 3. Тогда его сумма цифр тоже имеет остаток 1 при делении на 3. Если сложить это число и его сумму цифр, то получится число, которое дает остаток 2 при делении на 3. Пусть теперь число имеет остаток 2 при делении на 3. Если же мы сложим его с его суммой цифр, то в итоге будет число, которое дает остаток 1 при делении на 3. Изначально на экране единица -- имеет остаток 1 при делении на 3. Получается мы нашли инвариант: на экране в любой момент времени будет число, не делящееся на 3 (будут чередоваться остатки 1 и 2). Но нетрудно заметить, что число 1234567890987654321 делится на 3, так как его сумма цифр равна 90 (1+2+...+9 = 45).

Ответ: Нет, не может.