Математикадан 34-ші халықаралық олимпиада, 1993 жыл, Стамбул

$n$ саны 1-ден үлкен бүтін сан болсын. Шеңбер бойымен ${{L}_{0}}$, $\ldots $, ${{L}_{n-1}}$ белгіленген $n$ шам орналасқан. Әрбір шам "қосылған" немесе "өшірілген" деген режимдерде бола алады. ${{S}_{0}}$, ${{S}_{1}}$, $\ldots $, ${{S}_{i}}$, $\ldots $ тізбегінің қадамдары келесі түрде анықталады. ${{L}_{j-1}}$ қосылғанда ${{S}_{j}}$ қадамы ${{L}_{j}}$ күйін өзгертетіндей ${{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$ қадамнан кейін барлық шамдар қосылатынын дәлелдеңіздер.