Азиатско-Тихоокеанская математическая олимпиада, 2025 год

Пусть $n \geq 3$ — целое число. На окружности расположены $n$ ячеек, и в каждой ячейке записано либо 0, либо 1. В одной из ячеек находится петух, который выполняет следующую операцию:
   $\bullet$ Если находится в ячейке, в которой записан 0, он меняет этот нолик на 1 и переходит на следующую ячейку против часовой стрелки.
   $\bullet$ Если петух находится в ячейке, в которой записан 1, он меняет эту единицу на 0 и переходит через одну ячейку против часовой стрелки.
   Докажите, что через достаточно большое число операций выполняется следующее утверждение: Если петух находится в ячейке $C$, то он совершит ровно три полных круга по окружности и снова окажется в $C$. Более того, к этому моменту каждая ячейка будет содержать то же самое значение, что и перед тем, как петух начал обходить эти три круга.

Комментарий/решение

\textbf{Задача.}

Пусть $n\ge 3$. На окружности расположены $n$ ячеек, в каждой записано $0$ или $1$.

В одной из ячеек находится петух. Он выполняет операции:

\begin{itemize}

\item если в текущей ячейке записан $0$, он заменяет его на $1$ и переходит в следующую

ячейку против часовой стрелки;

\item если в текущей ячейке записана $1$, он заменяет её на $0$ и переходит через одну

ячейку против часовой стрелки.

\end{itemize}

Докажите, что через достаточно большое число операций выполняется следующее:

если петух находится в ячейке $C$, то он совершит ровно три полных круга и снова

окажется в $C$, причём к этому моменту все значения в ячейках будут такими же,

как перед началом этих трёх кругов.

\bigskip

\textbf{Решение.}

Пронумеруем ячейки числами $0,1,\dots ,n-1$ по модулю $n$.

Пусть петух находится в ячейке $i$, а вектор

\[

(a_0,a_1,\dots ,a_{n-1})

\]

описывает содержимое ячеек, где $a_j\in\{0,1\}$.

Состояние системы определяется парой

\[

(i,a_0,a_1,\dots ,a_{n-1}).

\]

Покажем, что отображение, соответствующее одному ходу петуха,

обратимо.

Действительно, если после хода петух оказался в ячейке $j$,

то возможны два случая:

\begin{itemize}

\item если переход был на одну ячейку, то перед этим в предыдущей

ячейке стоял $0$, который был заменён на $1$;

\item если переход был через одну ячейку, то перед этим в предыдущей

ячейке стояла $1$, которая была заменена на $0$.

\end{itemize}

В обоих случаях предыдущую позицию и значение в ячейке можно

восстановить однозначно. Следовательно, переход между состояниями

является биекцией.

Число всех возможных состояний конечно и равно

\[

n\cdot 2^n.

\]

Поэтому при бесконечном выполнении операций система обязательно

попадёт в некоторое состояние, которое уже встречалось раньше.

Начиная с этого момента движение становится периодическим.

Пусть период начинается в момент, когда петух находится в

ячейке $C$. Рассмотрим перемещение петуха за один период.

Заметим, что если в ячейке был $0$, петух проходит одну

ячейку, а если был $1$, он проходит две ячейки. При этом

значение в каждой посещённой ячейке меняется на противоположное.

В течение одного полного обхода окружности каждая ячейка

посещается нечётное число раз, поэтому её значение меняется

на противоположное. Следовательно, после одного круга все

значения инвертируются.

После второго круга они снова инвертируются, а после третьего

возвращаются к исходным. Таким образом, после трёх полных

кругов конфигурация ячеек совпадает с исходной.

Так как система находится в периодическом режиме, возвращение

конфигурации означает, что и положение петуха также совпадает

с исходным. Следовательно, начиная с некоторого момента,

если петух находится в ячейке $C$, он совершает ровно три

полных круга и снова оказывается в $C$, причём все значения

в ячейках совпадают с исходными.

\hfill $\square$