9 - Problem E: Solution

Summary

It is usually best to try some simple cases first. The case of two lights is trivial, for we can use switch 1 to change light 2, and switch 2 to change light 1. Now try the cases of three lights, and of four lights, to gain further insight into the problem. It seems that if n = 3 it is impossible to change all of the lights from ON to OFF, while it is possible to do this when n = 4. This suggests that the solution might depend on whether n is even or odd, so you should now try other cases to provide evidence for, or against, this suggestion. Note that to prove that it is possible to switch all of the lights OFF you only have to say which switches to use, and in which order to use them. How will you be able to prove that it is impossible to do something?

We should also be thinking about how to express this problem in a mathematical way. If we label the lights as L₁,L₂, … , L_n then we can record the state of the system as a vector (x₁, … , x_n), where x_j = 0 if the light L_j is OFF, and x_j = 1 if L_j is ON. For example, the vector (0, 1, 0, 1, 1, 1) represents six lights L₁, … , L₆, with L₂, L₄, L₅ and L₆ ON, and L₁ and L₃ OFF. The set S of possible states of a system with n lights is the set

which has exactly 2n elements. We shall consider the cases when n is even, and when n is odd, separately.

Case 1: n is even If we use each switch exactly once then each light will change its state n − 1 times, regardless of the order in which we use the switches. As n − 1 is odd, each light will therefore change its state. In particular, if all the lights are ON then we can switch them all OFF. Note that in this solution we use each switch once, and the switches can be used in any order.