Solution to November 2004 Problem
For this month’s problem we travel to the world’s first mathematics museum, the Mathematikum in Giessen, Germany. One exhibit there displays 7 lights evenly spaced about a circle. In front of each is a button that, when pushed, changes the state of its light and that of its two neighbors – a push of the button turns off any of the three that are on, and turns on any of the three that is off. If we begin with all lights switched off, what is the least number of buttons to push that will turn them all on? In what order should they be pushed?
Of course, it is natural to ask what happens to your answer when 7 is replaced by n: you have n lights around the table and n buttons to push. What is the least number of buttons that must be pushed to change from n lights al off to n lights all on? Describe how to do it, and provide a convincing argument why nobody can do it in fewer steps.
Solution to MP45
We received correct solutions from Alexander Akulov
(Regina), Pierre Bornsztein (France), Xavier Hecquet (France), Wolfgang
Kais (Germany), Patrick LoPresti (USA), and Juan Mir Pieras (Spain).
Let’s go straight to the general case with n buttons around the
table and their n associated lights. Initially all the lights are off.
All solvers noted immediately that in order to reach the state in which
all lights are on, every light has to change its state an odd number
of times. What matters, therefore, is what buttons we push, not the
order in which we push them. Moreover, pushing a button twice has the
same effect as not pushing it at all, so in a minimal solution the
number of times a button gets pushed is 0 or 1. At this point in the
argument, three of the submitted solutions introduced a form of mod
2 arithmetic, while the other three continued in a conversational style.
We shall look at both approaches.
The proof of Akulov, Kais, and Mir.
Each light is influenced by 3 buttons and every button influences 3 lights. Pushing every button exactly once will activate every light exactly 3 times, so in the end they will all be turned on. The question is only whether we can reach this state by pushing fewer than n buttons. Changing the state of every light only once means pushing n/3 buttons, which is possible exactly when n is a multiple of 3. Therefore, if n is not a multiple of 3, the state of at least one light must be changed 3 times, which means that we will have to push all three buttons which control that light. However, pushing 3 consecutive buttons will light the middle light of the three, and turn off its two neighbors. This starts a chain reaction that does not stop until all n buttons have been pushed. Our conclusion:
If n is a multiple of 3, pushing every third button (starting anywhere) will achieve the desired result most efficiently, and if n is not a multiple of 3, we must push all n buttons once. In particular, when n = 7, every button must be pushed once (in any order).
The proof of Bornsztein, and Hecquet.
We select an arbitrary button to be 0 and label the buttons counterclockwise from 0 to n – 1. We denote by xk the number of times the button labeled k is pushed; that is, xk represents either a 0 or a 1. The final state of light number k depends only on the parity of xk-1 + xk + xk+1 (where the subscripts are taken modulo n). Consequently, for all lights to be turned on it is necessary that in the cyclic sequence x0, x1, ... , xn–1, the sum of three consecutive terms must always be odd. This implies that in every triple of consecutive terms, the third term is uniquely determined by the first two: 0,0 leads to 0,0,1; 0,1 leads to 0,1,0; 1,0 leads to 1,0,0; and 1,1 leads to 1,1,1. The entire sequence is therefore completely determined by the values of x0 and x1., which means that the only possible sequences are
0,0,1,0,0,1,0,0,1,...
0,1,0,0,1,0,0,1,0,...
1,0,0,1,0,0,1,0,0,...
1,1,1,1,1,1,1,1,1,...
One sees easily that if n is not a multiple of 3, only the last sequence is possible. This sequence corresponds to pushing each button once, which, as observed earlier, turns on all the lights as desired. Since it is the only possible solution when n is not a multiple of 3, it must be minimal. If, on the other hand, n is a multiple of 3, the first three furnish a solution with n/3 buttons pushed.
Comments.
LoPresti’s argument was longer, but he proved more: when n is not a multiple of 3, each of the 2n possible arrangements of lit and unlit lights can be achieved by exactly one of the 2n possible selections of buttons (that is, by exactly one of the cyclic sequences of 0s and 1s.) On the other hand, when n is divisible by 3, not all of the possible outcomes can be achieved (which is obvious since the state in which all lights are lit can be reached with all four of the sequences listed earlier). He goes on to say that he has a “cute proof” of the assertion that it is possible to go from the all-off state to the all-on state no matter how the buttons are connected. More precisely, consider an arbitrary graph with the property that touching any node toggles that node and all nodes adjacent to it. Then there exists a sequence of nodes that you can touch to change the state of every node in the graph. (Our problem corresponds to the case where the graph is a cycle of length n.) Bornsztein also mentions this generalization, and he provides the reference
K. Sutner, Linear cellular automata and the Garden-of-Eden, The Mathematical Intelligencer, 12:2 (1989), p. 49-53.
He says that the proof found there can be considerably simplified. He goes on to say that the minimum number of operations needed is not known in general.