International Mathematical Olympiad 1993 Problem 6

There are $n$ lamps $L_0, \ldots, L_{n-1}$ in a circle ($n > 1$), where we denote $L_{n+k} = L_k$. (A lamp at all times is either on or off.) Perform steps $s_0, s_1, \ldots$ as follows: at step $s_i$, if $L_{i-1}$ is lit, switch $L_i$ from on to off or vice versa, otherwise do nothing. Initially all lamps are on. Show that:

(a) There is a positive integer $M(n)$ such that after $M(n)$ steps all the lamps are on again;

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

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