MathDB
ILL 92 NET 2 - Lamps

Source:

September 2, 2010
combinatoricsinvariantSystemalgorithmIMO ShortlistIMO Longlist

Problem Statement

Let nn be an integer >1> 1. In a circular arrangement of nn lamps L0,⋯ ,Ln−1L_0, \cdots, L_{n-1}, each one of which can be either ON or OFF, we start with the situation that all lamps are ON, and then carry out a sequence of steps, Step0,Step1,⋯Step_0, Step_1, \cdots. If Lj−1L_{j-1} (jj is taken mod n) is ON, then StepjStep_j changes the status of LjL_j (it goes from ON to OFF or from OFF to ON) but does not change the status of any of the other lamps. If Lj−1L_{j-1} is OFF, then StepjStep_j does not change anything at all. Show that:
(a) There is a positive integer M(n)M(n) such that after M(n)M(n) steps all lamps are ON again.
(b) If nn has the form 2k2^k, then all lamps are ON after n2−1n^2 - 1 steps.
(c) If nn has the form 2k+12^k +1, then all lamps are ON after n2−n+1n^2 -n+1 steps.
Back to ProblemsView on AoPS