« Vrati se
Let n > 1 be an integer. In a circular arrangement of n lamps L_0, \ldots, L_{n-1}, each of of which can either ON or OFF, we start with the situation where all lamps are ON, and then carry out a sequence of steps, Step_0, Step_1, \ldots . If L_{j-1} (j is taken mod n) is ON then Step_j changes the state of L_j (it goes from ON to OFF or from OFF to ON) but does not change the state of any of the other lamps. If L_{j-1} is OFF then Step_j does not change anything at all. Show that:

(i) There is a positive integer M(n) such that after M(n) steps all lamps are ON again,

(ii) If n has the form 2^k then all the lamps are ON after n^2-1 steps,

(iii) If n has the form 2^k + 1 then all lamps are ON after n^2 - n + 1 steps.

Slični zadaci

#NaslovOznakeRj.KvalitetaTežina
2299IMO Shortlist 2009 problem C30
2244IMO Shortlist 2007 problem C43
2187IMO Shortlist 2005 problem C65
2184IMO Shortlist 2005 problem C35
1917IMO Shortlist 1995 problem NC53
1862IMO Shortlist 1993 problem C50