34-я Международная Математическая OлимпиадаТурция, Стамбул, 1993 год

Пусть $n$ — целое число, большее 1. По окружности расположены $n$ ламп ${{L}_{0}}$, $\ldots$, ${{L}_{n-1}}$. Каждая лампа может быть в состоянии «включена» или «выключена». Последовательность шагов ${{S}_{0}}$, ${{S}_{1}}$, $\ldots$, ${{S}_{i}}$, $\ldots$ определяется следующим образом. Шаг ${{S}_{j}}$ влияет только на состояние лампы ${{L}_{j}}$ (и не влияет на состояние остальных ламп) так, что когда ${{L}_{j-1}}$ включена, шаг ${{S}_{j}}$ изменяет состояние ${{L}_{j}}$: если ${{L}_{j}}$ была включена, то станет выключена; если ${{L}_{j}}$ была выключена, то станет включена; когда же ${{L}_{j-1}}$ выключена, шаг ${{S}_{j}}$ ничего не меняет. (Лампы пронумерованы по модулю $n$, т. е. ${{L}_{-1}}={{L}_{n-1}}$, ${{L}_{0}}={{L}_{n}}$, ${{L}_{1}}={{L}_{n+1}}$ и т. д.)
Сначала все лампы были включены. Доказать, что:
а) существует положительное целое число $M\left( n \right)$ такое, что после $M\left( n \right)$ шагов опять все лампы будут включены;
б) если $n$ — число вида ${{2}^{k}}$, то после ${{n}^{2}}-1$ шагов все лампы будут включены;
в) если $n$ — число вида ${{2}^{k}}+1$, то после ${{n}^{2}}-n+1$ шагов все лампы будут включены.