На доске записано некоторое натуральное число N. Учитель по очереди вызывает учеников, которые выполняют с любым из уже записанных на доске чисел одно из следующих действий:
-- умножить число на 4;
-- прибавить к числу 12;
-- если число не равно 9, то вычеркнуть из числа цифру 9.
Затем ученик записывает новое число на доску.
а) Можно ли за несколько действий получить из числа 47 число 2?
б) Можно ли за несколько действий получить из числа 7 число 77?
в) Какое наибольшее количество чисел, меньших 2015, может быть записано на доске, если N=1?
Решение
а) Да, приведём пример получения 2 из 47: 47+125995+1217+122992.
б) Покажем, что каждое из действий не меняет остатка при делении на 3:
x+12≡x(mod3);
Вычёркивание цифры 9 уменьшает сумму цифр на 9, то есть сохраняет остаток от деления на 3, так как 9⋮3; 4x=3x+x≡x(mod3).
Заметим, что 7≡1(mod3) и 77≡2(mod3), значит, из 7 получить 77 невозможно.
б) На доске могут быть записаны лишь числа, имеющие остаток 1 при делении на 3:1,4,…,2011,2014=3⋅671+1, значит, всего максимум мы можем получить 672 числа.
Из 1 мы можем получить 4 умножением на 4.
Укажем последовательности получения чисел 7 и 10: 1+1213+1225+1237+1249+1261+1273+1285+129797; 1+12…+1297+12109910. Все последующие числа мы можем получить из 1,4,7 и 10 прибавлением 12 нужное количество раз.
