ILL 1992 Problem 52

Let $n$ be an integer $> 1$ . In a circular arrangement of $n$ lamps $L_0, \cdots, L_{n-1}$ , each one of which can be either ON or OFF, we start with the situation that all lamps are ON, and then carry out a sequence of steps, $Step_0, Step_1, \cdots$ . If $L_{j-1}$ ( $j$ is taken mod n) is ON, then $Step_j$ changes the status of $L_j$ (it goes from ON to OFF or from OFF to ON) but does not change the status of any of the other lamps. If $L_{j-1}$ is OFF, then $Step_j$ does not change anything at all. Show that:

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

(b) If $n$ has the form $2^k$ , then all lamps are ON after $n^2 - 1$ steps.

*(c)*If $n$ has the form $2^k +1$ , then all lamps are ON after $n^2 -n+1$ steps.