На окружности выписаны в произвольном порядке четыре единицы и пять нулей.
Затем в промежутке между двумя одинаковыми числами пишется единица,
а между разными цифрами — нуль, а первоначальные цифры стираются.
Доказать, что, сколько бы раз мы ни повторяли этот процесс,
мы никогда не получим набора из девяти единиц.
Е. Б. Дынкин, С. А. Молчанов, А. Л. Розенталь, А. К. Толпыго
Математические задачи. 3-е изд. – М.: Наука, 1971.
Мы поменяли местами в формулировке слова «единицы» и «нули». Это, конечно, не меняет существа задачи и сделано для того, чтобы не возникло путаницы при сопоставлении задач M19 и M56, о котором будет идти речь ниже.
Легко доказать даже более сильное утверждение: если на окружности выписано нечётное число $N$ единиц и нулей, причём встречаются и нули, и единицы, то, сколько бы раз мы ни повторяли описанный в задаче процесс, мы не получим набора из $N$ нулей. Действительно, предположим, что на каком-то $t$-м шаге мы впервые получили набор из одних нулей. Тогда на $(t-1)$-м шаге все $N$ цифр были одинаковы, и не все равны 0, поэтому они все были равны 1, а на $(t-2)$-м шаге каждые две соседние цифры должны были быть различными, но поскольку $N$ нечётно, то такого расположения 0 и 1 на окружности не существует.
Одновременно мы ответили (пока только для нечётного $N$) на вопрос, который остался неразобранным в решении M19 («Квант» №11, 1970, стр. 37—38); в этой задаче нули называются «покоящимися клетками», единицы — «возбужденными клетками», а правила перехода в точности те же самые. В этих терминах наш результат формулируется так: если $N$ нечётно, и в начальный момент не все клетки возбуждены (и не все покоятся), то возбуждение никогда не затухнет.
Что же будет при других $N$? Чтобы выяснить это, воспользуемся такой леммой (её можно доказать индукцией по $k$); она справедлива и для задачи на прямой, и для окружности; если при $t=0$ на $2^{k-1}$-м месте в ту и другую сторону от данной цифры $a$ стоят одинаковые цифры, то через $t=2^k$ шагов на месте $a$ будет стоять нуль, а если разные, то единица. Отсюда сразу следует, что если $N=2^m$, где $m$ — натуральное, то из любого набора за $N$ шагов получится набор из одних нулей.
Пусть теперь $N=2^m L$, где $L$ — нечётно. Проследим за изменениями, которые происходят за каждые $T=2^m$ шагов. Для каждой $L$ цифр, расположенных через $2^m$ друг от друга (в вершинах правильного $L$-угольника), эти изменения будут в точности такими же, как будто только эти $L$ цифры расположились по окружности, с ними повторялся тот же процесс, и мы следили за каждым шагом. Отсюда нетрудно получить ответ в самом общем случае: состояние «все нули» достигается в том и только в том случае, если начальная последовательность из 0 и 1 была периодической с периодом $2^m$ (см. рис. 4).
Рис. 4. Нули и единицы на левом рисунке через 8 шагов превратятся во все нули.
