9. На бесконечной ленте записаны в ряд 3 цифры. Справа к ним приписывают цифру, на которую оканчивается их сумма, а первую цифру после этого стирают. а) Докажите, что когда-то цифры начнут повторяться по циклу. б) Докажите, что после некоторого числа таких операций на ленте снова будут записаны те же цифры, что и вначале. в) Докажите, что для этого потребуется не более 1000 операций.

Обозначим три цифры на ленте через a, b, c. После операции получается состояние (b, c, d), где d — последняя цифра суммы a + b + c.

1. а) Возможных троек цифр всего 10 · 10 · 10 = 1000. При каждой тройке следующая определяется однозначно. Поэтому среди состояний последовательности рано или поздно встретится повтор. С этого момента тройки будут повторяться циклически.
2. б) Переход от тройки (a, b, c) к (b, c, d) обратим: по новой тройке можно восстановить первую цифру прежней тройки как остаток от d − b − c при делении на 10. Значит, переход задаёт перестановку всех 1000 троек. При перестановке каждая тройка находится в цикле с самого начала, поэтому исходная тройка обязательно появится снова.
3. в) Цикл содержит не более 1000 различных троек, поскольку всего возможны 1000 состояний. Следовательно, исходная тройка вернётся не позднее чем через 1000 операций.