Пункт а
Да, можно. Например, так:
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.
