Question 6
Let $n$ be an integer greater than $1$. In a circular arrangement of $n$ lamps $L_0,\ldots,L_{n-1}$, each one of that can be either ON or OFF, we start with the situation where all lamps are ON, and then carry out a sequence of steps, $\mathrm{Step}_0,\mathrm{Step}_1,\ldots$. If $L_{j-1}$ ($j$ is taken mod $n$) is ON, then $\mathrm{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 $\mathrm{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.
(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.