қазақша
русскийМатематикадан 34-ші халықаралық олимпиада, 1993 жыл, Стамбул
Бстапқыда барлық шамдар қосылған.
а) $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), (б) и (в) доказаны.
Возможно, что при неправильном наборе формул, они будут
доредактированы модератором. При этом содержание не будет меняться.