Задание №53481. Числа и их свойства
На доске записано некоторое натуральное число \(N\). Учитель по очереди
вызывает учеников, которые выполняют с любым из уже записанных на доске чисел
одно из следующих действий: умножить число на \(4\); прибавить к числу \(12\);
если число не равно \(9\), то вычеркнуть из числа цифру \(9\). Затем ученик
записывает новое число на доску.
а) Можно ли за несколько действий получить из числа \(47\) число \(2\)?
б) Можно ли за несколько действий получить из числа \(7\) число \(77\)?
в) Какое наибольшее количество чисел, меньших \(2015\), может быть записано
на доске, если \(N=1\)?
Шаг 1. Главное наблюдение: ни одно из трёх действий не меняет остатка числа при делении на \(3\).
Умножение на \(4\): \(4x-x=3x\) делится на \(3\).
Прибавление \(12\): число \(12\) делится на \(3\).
Вычёркивание цифры \(9\): при вычёркивании сумма цифр уменьшается на \(9\), а число сравнимо со своей суммой цифр по модулю \(9\), значит и по модулю \(3\); остаток не меняется.
Итак, остаток при делении на \(3\) — инвариант.
а) Да. Вот цепочка:
\[47\xrightarrow{+12}59\xrightarrow{\text{вычёркиваем }9}5\xrightarrow{+12}17\xrightarrow{+12}29\xrightarrow{\text{вычёркиваем }9}2.\]
Все числа дают остаток \(2\) при делении на \(3\), что согласуется с инвариантом.

б) Нет. Число \(7\) даёт остаток \(1\) при делении на \(3\), а число \(77\) — остаток \(2\) (так как \(77=3\cdot25+2\)). Остатки различны, а по шагу 1 остаток измениться не может.
в) Наибольшее количество равно \(672\).
Оценка. Начальное число \(N=1\) даёт остаток \(1\) при делении на \(3\), поэтому и все числа на доске дают остаток \(1\). Значит, на доске могут встретиться только числа вида \(3k+1\). Меньших \(2015\) среди них ровно столько, сколько натуральных чисел в списке
\[1,\ 4,\ 7,\ \dots,\ 2014,\]
то есть \(\dfrac{2014-1}{3}+1=672\).
Пример. Покажем, что все эти \(672\) числа действительно можно получить. Достаточно получить четыре «стартовых» числа \(1\), \(4\), \(7\) и \(10\): из каждого из них прибавлением двенадцати получаются все числа, дающие при делении на \(12\) тот же остаток, а остатки \(1,\ 4,\ 7,\ 10\) по модулю \(12\) — это в точности все остатки, отвечающие остатку \(1\) при делении на \(3\).
Число \(1\) дано. Умножив его на \(4\), получаем \(4\).
Прибавив к \(1\) двенадцать восемь раз, получаем \(1+96=97\); вычёркиваем цифру \(9\) и получаем \(7\).
Прибавив к \(1\) двенадцать девять раз, получаем \(1+108=109\); вычёркиваем цифру \(9\) и получаем \(10\).
Все промежуточные числа меньше \(2015\), так что построение остаётся в нужных пределах.
Итак, все \(672\) числа достижимы, а других чисел, меньших \(2015\), на доске появиться не может.