Switching the lights on and off
Source: Romania TST 1 2009, Problem 3
May 4, 2012
inductionlinear algebramatrixcombinatorics
Problem Statement
Some lamps are cyclically connected: lamp with lamp , ..., lamp with lamp ,..., lamp with lamp , lamp with lamp . At the beginning all lamps are off. When one pushes the switch of a lamp, that lamp and the two ones connected to it change status (from off to on, or vice versa). Determine the number of configurations of lamps reachable from the initial one, through some set of switches being pushed.