20 - Problem E: Discussion and Generalisations

Summary

First, the solution to the problem of the cube is easy. If we use every switch once, then each light will change three times, and hence each light will change from ON to OFF. In fact, if we operate the three switches that are adjacent to a given vertex this has the same effect as a normal switch at that vertex; thus we can pass from any one state of the lights to any other state.

Let us continue by addressing the question: if, in the original problem, n is odd, can we pass from any even state to any other even state, and from any odd state to any other odd state? It is always a good idea to experiment with some special cases, so here is one. Suppose that n = 5 and that A = (1, 0, 1, 0, 1) and B = (1, 1, 1, 0, 0): can we pass from A to B? Let us agree to use switch 1 k₁ times, switch 2 k₂ times, and so on, where each k_j is 0 or 1. We will pass from A to B with this choice of switches if and only if we can solve the congruence equation

where the k_j are the ‘unknowns’ (and each is 0 or 1). This equation is equivalent to the equation

or to the system

taken modulo 2. By subtraction we see that k1 = k3 = k4 and k2 = k5, and hence the unique solution (modulo 2) is k2 = k5 = 1 and k1 = k3 = k4 = 0. Thus we should use only switches 2 and 5, and it is easy to check that this combination does indeed take us from state A to state B. More generally, if we consider any two states A and B and write A + B = C = (c1, c2, c3, c4, c5), then we obtain the equations

If we now add all of these equations together, we find that a necessary condition for a solution is that c1 +· · ·+c5 = 0 (mod 2). This confirms that (with n = 5) we can only pass between even states, and between odd states.