Loading [MathJax]/jax/output/SVG/jax.js

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


n саны 1-ден үлкен бүтін сан болсын. Шеңбер бойымен L0, , Ln1 белгіленген n шам орналасқан. Әрбір шам "қосылған" немесе "өшірілген" деген режимдерде бола алады. S0, S1, , Si, тізбегінің қадамдары келесі түрде анықталады. Lj1 қосылғанда Sj қадамы Lj күйін өзгертетіндей Sj қадамы тек Lj шамының күйіне әсер ете алады (басқа шамдардың күйлеріне әсер етпейді): егер Lj қосылған болса, онда өшіріледі; егер Lj өшірілген болса, онда қосылады; егер Lj1 өшірілгенде Sj ештене өзгертпейді. (Шамдар n бойынша модульдер бойынша нөмірленген, яғни L1=Ln1, L0=Ln, L1=Ln+1 және т.б.)
Бстапқыда барлық шамдар қосылған.
а) M(n) қадамнан кейін шамдар қайтадан қосылатындай M(n) бүтін оң саны табылатынын дәлелдеңіздер;
б) Егер n саны 2k түріндегі сан болса, онда n21 қадамнан кейін барлық шамдар қосылатынын дәлелдеңіздер;
в) Егер n саны 2k+1 түріндегі сан болса, онда n2n+1 қадамнан кейін барлық шамдар қосылатынын дәлелдеңіздер.
посмотреть в олимпиаде

Комментарий/решение: