Пункт а

Да, можно. Например, так:

47 → (+12) → 59 → (вычеркнуть 9) → 5

5 → (+12) → 17 → (+12) → 29

29 → (вычеркнуть 9) → 2

Пункт б

Нет, нельзя. Покажем, что все три операции сохраняют остаток при делении на 3 — тогда этот остаток является инвариантом и изменить его невозможно.

Умножение на 4. Так как \(4 \equiv 1 \pmod 3\), то \(4n \equiv n \pmod 3\).

Прибавление 12. Число 12 делится на 3, поэтому остаток не меняется.

Вычёркивание девятки. Здесь само число меняется сильно — например, из 2293 получается 223. Но нам важен не сам результат, а остаток.

Вспомним признак делимости на 3 в сильной форме: число даёт при делении на 3 тот же остаток, что и сумма его цифр. Это следует из того, что \(10 \equiv 1 \pmod 3\), а значит и \(100 \equiv 1\), \(1000 \equiv 1\) и так далее — каждый разряд вносит в остаток ровно свою цифру. Например, \(2293\) и \(2+2+9+3 = 16\) дают один и тот же остаток 1.

При вычёркивании девятки из суммы цифр пропадает ровно 9, а всё остальное остаётся на месте. Значит сумма цифр уменьшается на 9 — на число, кратное трём, — и её остаток не меняется. А вместе с ним не меняется и остаток самого числа.

Итак, у всех чисел на доске один и тот же остаток при делении на 3. Но \(7\) даёт остаток 1, а \(77\) — остаток 2, ведь \(77 = 75 + 2\). Получить 77 из 7 невозможно.

Пункт в. Оценка сверху

По пункту б) все числа на доске сравнимы с \(N = 1\) по модулю 3, то есть дают остаток 1. Меньших 2015 таких чисел ровно

\[1,\ 4,\ 7,\ \ldots,\ 2014.\]

Это арифметическая прогрессия с первым членом 1 и разностью 3. Чтобы сосчитать, сколько в ней членов, посмотрим, сколько шагов по 3 нужно сделать от 1 до 2014: это \(\dfrac{2014 - 1}{3} = 671\) шаг. Шагов 671, а чисел на один больше, потому что считается и само начальное число:

\[\frac{2014 - 1}{3} + 1 = 672.\]

Значит больше 672 различных чисел записать нельзя — просто потому, что подходящих чисел всего столько. Осталось показать, что все 672 действительно можно выписать.

Пункт в. Как записать все 672

Прибавление 12 и умножение на 4 только увеличивают число, «спускаться» вниз позволяет лишь вычёркивание девятки. Идея такая: длинными сериями прибавлений по 12 заполняем арифметические прогрессии с шагом 12, а вычёркиванием девятки перескакиваем в следующую прогрессию.

Почему появляется именно число 12? Потому что прибавление 12 не меняет остаток при делении на 12: двигаясь этой операцией, мы всё время остаёмся в одной и той же прогрессии с шагом 12. Значит одной серией прибавлений всю нужную нам тысячу чисел не покрыть, и надо понять, сколько таких прогрессий требуется.

Нас интересуют числа с остатком 1 при делении на 3. Посмотрим, какие остатки по модулю 12 у них могут быть. Остаток по модулю 12 — это число от 0 до 11; из них на 3 с остатком 1 делятся четыре:

\[1, \qquad 4, \qquad 7, \qquad 10.\]

Остальные восемь остатков дают при делении на 3 остаток 0 или 2, а такие числа на доске появиться не могут. Итак, все нужные числа лежат в четырёх прогрессиях с шагом 12, и каждую из них надо пройти целиком.

Подпись «+12 много раз» означает, что прибавление 12 применяется подряд несколько раз, и все промежуточные числа тоже оказываются на доске. Например, запись «1 → (+12 много раз) → 2293» расшифровывается так: сначала пишем 1, потом 13, потом 25 и так далее, пока не дойдём до 2293. Всего это 191 прибавление, ведь \(2293 - 1 = 2292\), а \(2292 : 12 = 191\).

1 → (+12 много раз) → 2293

2293 → (вычеркнуть 9) → 223

По дороге выписаны все числа \(1,\ 13,\ 25,\ \ldots,\ 2005\) — это прогрессия с остатком 1 по модулю 12.

223 → (+12 много раз) → 9799

9799 → (вычеркнуть 9) → 799

799 → (вычеркнуть 9) → 79

79 → (вычеркнуть 9) → 7

Выписаны \(223,\ 235,\ \ldots,\ 2011\), а тройное вычёркивание девятки спускает нас к семёрке.

7 → (+12 много раз) → 211

211 → (умножить на 4) → 844

844 → (+12 много раз) → 904

904 → (вычеркнуть 9) → 4

Добраны оставшиеся \(7,\ 19,\ \ldots,\ 199\) — вместе с предыдущей серией это вся прогрессия с остатком 7 по модулю 12. Теперь выписаны все 336 нечётных подходящих чисел, и мы перешли к четвёрке.

4 → (+12 много раз) → 2008

2008 → (+12 много раз) → 2092

2092 → (вычеркнуть 9) → 202

Выписаны \(4,\ 16,\ \ldots,\ 2008\) — прогрессия с остатком 4 по модулю 12.

202 → (+12 много раз) → 9022

9022 → (вычеркнуть 9) → 22

22 → (+12 много раз) → 190

190 → (вычеркнуть 9) → 10

Выписаны \(202,\ 214,\ \ldots,\ 2014\), затем \(22,\ 34,\ \ldots,\ 190\) и, наконец, само число 10 — это вся прогрессия с остатком 10 по модулю 12, то есть все 336 чётных подходящих чисел.

Все четыре прогрессии покрыты, выписаны все 672 числа. Значит оценка достигается.

Ответ: а) да;   б) нет;   в) 672.