IMO 1993 Problem 6

Let $n > 1$ be an integer. In a circular arrangement of $n$ lamps $L_0, \ldots, L_{n-1},$ each of of which is either ON or OFF. Denote $L_{k+n}=L_k$. Initially all lamps are ON. We carry out a sequence of steps. At step $j$ if $L_{j-1}$ is ON then the state of $L_j$ is changed, otherwise do nothing. Show that:

(i) There is a positive integer $M(n)$ such that after $M(n)$ steps all lamps are ON again,

(ii) If $n=2^k$ then we can take $M(n)=n^2-1$,

(iii) If $n=2^k+1$ then we can take $M(n)=n^2 - n + 1$.

==========================================

(i) Combined with number of steps modulo $n$ there are finitely many states, and the transition function between states is one-one. Hence at some point we return to the initial state where all lamps are ON.

(ii) We use $L_i=1$ and $L_i=0$ to denote the state of lamp $i$ being ON and OFF, respectively. By a round we mean the process of potentially updating $L_0,L_1,\dots,L_{n-1}$. Every round has $n$ steps except for the first, which has $n-1$ steps. We prove these properties inductively

$$P_{n,a}: L_{n-1}=0 \text{ after step }1,2,\dots,n^2-2,$$

$$P_{n,b}:\text{ all lamps are ON after step }n^2-1.$$

$P_{n,b}$ is equivalent to that after round $n-1$ all lamps but the first are OFF. Now with $2n$ lamps, after step $1$ we see that $L_{i}=L_{i+n}$ for $i=0,1,\dots,n-1$, in particular $L_{n-1}=L_{2n-1}=0$. Combining the latter with $P_{n,a}$, we see that after round $n-1$ all lamps but $L_0$ and $L_{n}$ are OFF. After round $n$, the first and second $n$ lamps are all ON and OFF, respectively. It could be seen that in the next $n-1$ rounds all second $n$ lamps are OFF, and after that all lamps but the first are OFF. After the next round, i.e., round $2n$, all lamps are ON again. Clearly $P_{2n,a}$ and $P_{2n,b}$ hold.

(iii) After the first round plus an extra step, $L_0=L_1=0$. Because $P_{n-1,a}$ holds, until all lamps on ON again we see that $L_0=L_1=0$ and $L_2,\dots,L_{n-1},L_0$ behave same as $L_0,L_1,\dots,L_{n-2}$ with $n-1$ lamps. Hence it takes about $n-1$ rounds for all lamps to light up. More precisely, the last step is to update $L_1$ according to $L_0$. Thus $$M(n)=1+n(n-1)=n^2-n+1.$$