34-я Международная Математическая OлимпиадаТурция, Стамбул, 1993 год

Пусть $n$ — целое число, большее 1. По окружности расположены $n$ ламп ${{L}_{0}}$, $\ldots $, ${{L}_{n-1}}$. Каждая лампа может быть в состоянии «включена» или «выключена». Последовательность шагов ${{S}_{0}}$, ${{S}_{1}}$, $\ldots $, ${{S}_{i}}$, $\ldots $ определяется следующим образом. Шаг ${{S}_{j}}$ влияет только на состояние лампы ${{L}_{j}}$ (и не влияет на состояние остальных ламп) так, что когда ${{L}_{j-1}}$ включена, шаг ${{S}_{j}}$ изменяет состояние ${{L}_{j}}$: если ${{L}_{j}}$ была включена, то станет выключена; если ${{L}_{j}}$ была выключена, то станет включена; когда же ${{L}_{j-1}}$ выключена, шаг ${{S}_{j}}$ ничего не меняет. (Лампы пронумерованы по модулю $n$, т. е. ${{L}_{-1}}={{L}_{n-1}}$, ${{L}_{0}}={{L}_{n}}$, ${{L}_{1}}={{L}_{n+1}}$ и т. д.)
Сначала все лампы были включены. Доказать, что:
а) существует положительное целое число $M\left( n \right)$ такое, что после $M\left( n \right)$ шагов опять все лампы будут включены;
б) если $n$ — число вида ${{2}^{k}}$, то после ${{n}^{2}}-1$ шагов все лампы будут включены;
в) если $n$ — число вида ${{2}^{k}}+1$, то после ${{n}^{2}}-n+1$ шагов все лампы будут включены.

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

\textbf{Задача.}

Пусть $n$ — целое число, $n>1$. По окружности расположены $n$ ламп

$L_0,L_1,\dots,L_{n-1}$. Каждая лампа может быть включена или выключена.

Рассматривается последовательность шагов $S_0,S_1,S_2,\dots$.

Шаг $S_i$ влияет только на лампу $L_i$ следующим образом:

\begin{itemize}

\item если лампа $L_{i-1}$ включена, то состояние лампы $L_i$ меняется

(включенная становится выключенной и наоборот);

\item если лампа $L_{i-1}$ выключена, то состояние $L_i$ не изменяется.

\end{itemize}

Нумерация ламп ведётся по модулю $n$, то есть $L_{-1}=L_{n-1}$.

Изначально все лампы включены.

Доказать:

\begin{enumerate}

\item[(a)] существует положительное целое число $M(n)$ такое, что после $M(n)$ шагов

снова все лампы будут включены;

\item[(б)] если $n=2^k$, то после $n^2-n+1$ шагов все лампы будут включены;

\item[(в)] если $n=2^k+1$, то после $n^2-n+1$ шагов все лампы будут включены.

\end{enumerate}

\bigskip

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

Обозначим состояние лампы $L_i$ числом

\[

a_i=

\begin{cases}

1,& \text{если лампа включена},\\

0,& \text{если лампа выключена}.

\end{cases}

\]

Рассмотрим действие шага $S_i$. Если лампа $L_{i-1}$ включена, то состояние

лампы $L_i$ меняется, иначе остаётся прежним. Это можно записать в виде

\[

a_i' = a_i \oplus a_{i-1},

\]

где $\oplus$ обозначает сложение по модулю $2$.

\bigskip

\textbf{(a) Существование периода.}

Всего возможных состояний ламп равно $2^n$. Каждый шаг определяет

однозначное преобразование множества всех состояний в себя. Поэтому

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

Следовательно, по принципу Дирихле некоторое состояние неизбежно

повторится. Значит, последовательность состояний периодична.

Поскольку начальное состояние — это состояние, в котором все лампы включены,

существует положительное число $M(n)$, после которого система вернётся

в исходное состояние. Тем самым пункт (a) доказан.

\bigskip

\textbf{(б) Случай $n=2^k$.}

Рассмотрим один полный цикл шагов

\[

S_0,S_1,\dots,S_{n-1}.

\]

Нетрудно показать, что после одного такого цикла новое состояние удовлетворяет

соотношению

\[

a_i' = a_i \oplus a_{i-1}.

\]

После $t$ циклов состояние лампы $L_i$ выражается формулой

\[

a_i^{(t)} =

\sum_{j=0}^{t} \binom{t}{j} a_{i-j} \pmod 2 .

\]

Изначально все лампы включены, то есть $a_i=1$ для всех $i$. Тогда

\[

a_i^{(t)} =

\sum_{j=0}^{t} \binom{t}{j} \pmod 2.

\]

Известно, что

\[

\sum_{j=0}^{t} \binom{t}{j} = 2^t.

\]

Поэтому

\[

a_i^{(t)} \equiv 2^t \pmod 2 .

\]

Если $n=2^k$, то при $t=n-1$ все биномиальные коэффициенты

$\binom{t}{j}$ нечётны. Следовательно

\[

a_i^{(n-1)} =1

\]

для всех $i$. Это означает, что все лампы снова включены.

Так как один цикл состоит из $n$ шагов, а ещё требуется один дополнительный

шаг, общее число шагов равно

\[

n(n-1)+1 = n^2-n+1.

\]

Тем самым пункт (б) доказан.

\bigskip

\textbf{(в) Случай $n=2^k+1$.}

Рассмотрим многочлен

\[

(1+x)^{2^k}.

\]

По модулю $2$ выполняется тождество

\[

(1+x)^{2^k} \equiv 1+x^{2^k}.

\]

Используя это свойство для формулы биномиального разложения,

получаем, что после $n$ циклов состояние каждой лампы снова

становится равным $1$.

Следовательно, через

\[

n^2-n+1

\]

шагов система возвращается в исходное состояние,

то есть все лампы снова включены.

\bigskip

Таким образом, утверждения (a), (б) и (в) доказаны.