\documentclass[11pt]{scrartcl}
\usepackage{evan}

\begin{document}
\title{IMO 1993/6}
\subtitle{Evan Chen}
\author{Twitch Solves ISL}
\date{Episode 45}
\maketitle

\section*{Problem}
Let $n > 1$ be an integer. In a circular arrangement of $n$ lamps
$L_0$, \dots, $L_{n-1}$ each of which can either be ON or OFF
and with indices taken modulo $n$,
we start with the situation where all lamps are ON,
and then carry out a sequence of steps.
On the $j$th step (for $j=0,1,\dots$)
if $L_{j-1}$ is ON then $L_j$ is toggled,
whereas if $L_{j-1}$ is OFF then nothing happens.
Show that:
\begin{enumerate}[(i)]
  \ii There is a positive integer $M(n)$ such that
  after $M(n)$ steps all lamps are ON again,
  \ii If $n$ has the form $2^k$ then all the lamps
  are ON after $n^2-1$ steps,
  \ii If $n$ has the form $2^k + 1$ then all lamps
  are ON after $n^2 - n + 1$ steps.
\end{enumerate}

\section*{Video}
\href{https://www.youtube.com/watch?v=OvHiDzshu7M&list=PLi6h8GM1FA6yHh4gDk_ZYezmncU1EJUmZ}{\texttt{https://youtu.be/OvHiDzshu7M}}

\section*{External Link}
\url{https://aops.com/community/p372299}

\newpage

\section*{Solution}
For part (i), the sequence of states (and time indices modulo $n$)
is finite, so it is certainly eventually periodic;
however, because the operation is invertible, it is totally periodic.

Throughout the problem we always work modulo $2$.
By a \emph{round} we mean a sequence of $n$ consecutive operations.
Note that a round has the following effect:
\begin{align*}
  (a_1, \dots, a_{n-1}, a_0)
  \mapsto (&a_2+a_3+\dots+a_0, \\
  & a_1 + a_2, \; a_1 + a_2 + a_3, \;
    \dots, \; a_1 + a_2 + a_3 + \dots + a_0).
\end{align*}
(We prefer to list $L_1$ first, rather than $L_0$.)

For (ii), we give a description of the process for $n = 2^{k+1}$
in terms of the process for $n = 2^k$.
We write our states as binary strings of length $n$,
with the $i$th bit corresponding to $L_i$
(the last bit corresponds to $L_n = L_0$).
The description goes as follows:
\begin{itemize}
  \ii We split the string into $L_1 L_2 \dots L_{n/2} \mid
    L_{n/2+1} \dots L_n$.
  \ii There are two copies of the process for $n=2^k$ side by side
  until we reach the string $100\dots \mid 1000$.
  \ii After the next round, we get $11\dots11 \mid 00\dots00$.
  \ii Then, the left half plays another copy of the $n=2^k$ process,
  with the right half being all zero,
  until we reach $1000 \mid 0000$
  \ii Then $n-1$ turns later we get $111\dots111$ as needed.
\end{itemize}

For concreteness,
if $n=4$ is given by
\[ 1111 \xmapsto{4\text{ moves}} 1010
  \xmapsto{4\text{ moves}} 1100
  \xmapsto{4\text{ moves}} 1000
  \xmapsto{3\text{ moves}} 1111
\]
in terms of the rounds, then $n=8$ is given by
\begin{align*}
  1111\mid1111
  &\xmapsto{8\text{ moves}} 1010\mid1010
  \xmapsto{8\text{ moves}} 1100\mid1100 \\
  &\xmapsto{8\text{ moves}} 1000\mid1000
  \xmapsto{8\text{ moves}} 1111\mid0000 \\
  &\xmapsto{8\text{ moves}} 1010\mid0000
  \xmapsto{8\text{ moves}} 1100\mid0000 \xmapsto{8\text{ moves}}
  1000\mid0000.
\end{align*}
and seven moves later we return to all $1$'s.
One can now check by a straightforward induction that
the number of moves is $n^2-1$ exactly.

For (iii), we give a description for $n=2^k+1$ in terms
of that for $n=2^k$.
All that needs to be observed is that the situation
after the $i$th round of $n=2^k+1$
is the same as the $i$th round of $n=2^k$,
except with last bit moved to the first, and one extra $0$ appended,
up until we reach the special state $0010000\dots$.
For example, for $n = 9$ we have
\begin{align*}
  111111111
  &\xmapsto{9\text{ moves}} 001010101
  \xmapsto{9\text{ moves}} 001100110 \\
  &\xmapsto{9\text{ moves}} 001000100
  \xmapsto{9\text{ moves}} 001111000 \\
  &\xmapsto{9\text{ moves}} 001010000
  \xmapsto{9\text{ moves}} 001100000 \xmapsto{9\text{ moves}} 001000000
\end{align*}
and then after an additional $n+1$ moves we return to all $1$'s.
The total move count can be computed to be the desired $n^2-n+1$.

\end{document}
