MathDB
n lamps numbered 1, 2, ..., n be connected in cyclic order , turn on off lamps

Source: Indian Postal Coaching 2009 set 5 p6

May 26, 2020
combinatorics

Problem Statement

Let n>2n > 2 and nn lamps numbered 1,2,...,n1, 2, ..., n be connected in cyclic order: 11 to 2,22, 2 to 3,...,n−13, ..., n-1 to n,nn, n to 11. At the beginning all lamps are off. If the switch of a lamp is operated, the lamp and its 22 neighbors change status: off to on, on to off. Prove that if 33 does not divide nn, then (all the) 2n2^n configurations can be reached and if 33 divides nn, then 2n−22^{n-2} configurations can be reached.
Back to ProblemsView on AoPS