Browse · MathNet
PrintEstonian Math Competitions
Estonia counting and probability
Problem
Let be a natural number, . There are lamps on a circle. The lamps are labeled clockwise by natural numbers from to . Each lamp can be either on or off. A switch between every two adjacent lamps enables one to change the state of both lamps simultaneously. In the beginning, all lamps are off. How many distinct configurations of states of lamps is it possible to achieve using these switches?
Solution
As the state of each lamp is determined by the parity of the number of switchings that influence this lamp, the result of every sequence of switchings is determined by the set of switches that have been touched an odd number of times. Hence all possible states can be achieved by sequences of switchings that touch some switches once and do not touch other switches at all, whereby the order of switchings is irrelevant.
Note that every two set of switches, one of which contains precisely the switches that the other one does not, lead to equal final states, because touching these two sets of switches in a row one touches each switch exactly once and thus changes the state of each lamp exactly twice. As there are sets of switches and these sets can be divided into pairs that give equal final states, there can be at most final states.
If two sets of switches are neither equal nor complementary (in the sense of previous paragraph) then touching these two sets of switches in a row does not give back the initial state, because this sequence of switchings is equivalent to touching a set of switches that contains some switch and does not contain some other switch, but then there must exist a lamp, the switch in only one side of which is touched. Hence every pair of sets of switches defined in the previous paragraph gives a unique final state, i.e., there are possible distinct final states.
---
Alternative solution.
After every switching, either two more lamps are burning, two less lamps are burning, or the number of burning lamps does not change. As the initial number of burning lamps is even, the number of burning lamps stays even.
We show that every state with an even number of burning lamps can be achieved. As the switchings are invertible (repeating the same touch reverts the previous change), it suffices to show that, starting from any state with an even number of burning lamps, one can achieve the state where no lamp is burning. Indeed, while there exist two consecutive burning lamps, we can switch off both these lamps. If there do not exist such lamps, but some lamps are still burning, one can shift a lonely burning lamp clockwise by repeatedly touching the clockwise nearest switch until two consecutive lamps are burning. Switching these two lamps off decreases the total number of burning lamps by . This way, we can decrease the number of burning lamps until all lamps are switched off.
Thus the number of all achievable states is which equals .
Note that every two set of switches, one of which contains precisely the switches that the other one does not, lead to equal final states, because touching these two sets of switches in a row one touches each switch exactly once and thus changes the state of each lamp exactly twice. As there are sets of switches and these sets can be divided into pairs that give equal final states, there can be at most final states.
If two sets of switches are neither equal nor complementary (in the sense of previous paragraph) then touching these two sets of switches in a row does not give back the initial state, because this sequence of switchings is equivalent to touching a set of switches that contains some switch and does not contain some other switch, but then there must exist a lamp, the switch in only one side of which is touched. Hence every pair of sets of switches defined in the previous paragraph gives a unique final state, i.e., there are possible distinct final states.
---
Alternative solution.
After every switching, either two more lamps are burning, two less lamps are burning, or the number of burning lamps does not change. As the initial number of burning lamps is even, the number of burning lamps stays even.
We show that every state with an even number of burning lamps can be achieved. As the switchings are invertible (repeating the same touch reverts the previous change), it suffices to show that, starting from any state with an even number of burning lamps, one can achieve the state where no lamp is burning. Indeed, while there exist two consecutive burning lamps, we can switch off both these lamps. If there do not exist such lamps, but some lamps are still burning, one can shift a lonely burning lamp clockwise by repeatedly touching the clockwise nearest switch until two consecutive lamps are burning. Switching these two lamps off decreases the total number of burning lamps by . This way, we can decrease the number of burning lamps until all lamps are switched off.
Thus the number of all achievable states is which equals .
Final answer
2^{n-1}
Techniques
Invariants / monovariantsRecursion, bijectionAlgebraic properties of binomial coefficientsGames / greedy algorithms