Азиатско-Тихоокеанская математическая олимпиада, 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$