IMO олимпиада по математике 1993 года | Казахстанские олимпиады

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