This month’s problem might help explain why it takes so many mathematicians to change a light bulb.

The submitted solutions differed only in notation.  Bornsztein and Kais discussed the problem in terms of a graph that has 27 vertices with labels ABC:  Each of A, B, and C represent a 0, 1, or 2, where A is the position of the first switch, B of the second, and C of the third.  Two vertices of the graph are connected by an edge when their labels differ in all three components.  The use of graphs makes some relationships easier to state, but it does not appear to simplify the solution.  Here we list the 27 states and place an X in the column of any colour that is eliminated by rule 2.  We begin with 000 – the initial state, in which all three switches are in position 0 -- having an R in the red column, and 100 with a Y in the yellow column.  By rule 2, any state with nonzero digits in all three places gets an X in the red column – these cannot correspond to a red light.  Similarly, those states with a number different from 1 in the first place and nonzero digits in the other two get X in the yellow column.  Here then is our initial state of knowledge:

Table 1

Since 211, 212, 221, and 222 can be neither red nor yellow, these states must produce a green light; thus they get a G in the green column.

            We now have four known green states 2BC; each of these allow us to deduce that many states cannot be green, namely 0(B ± 1)(C ± 1) and 1(B ± 1)(C ± 1), where the sums are reduced modulo 3.  In fact these are all the states that begin with 0 or with 1 – we conclude that any state beginning with 0 or 1 cannot be green. 

Table 2

This allows us to conclude that 011, 012, 021, and 022 must represent red, and 111, 112, 121, and 122 represent yellow.

            Our new knowledge allows us to deduce that any triple that begins with 1 or 2 cannot be red (since 100, 102, and 120 differ from 011 in all three places, while 101 and 110 differ from 022 in all three places, and same with 200, 202, 220, 201, and 210).  Similarly, any triple that begins with a 0 or 2 cannot be yellow.  That leads us to the conclusion

If the first switch is in position 0 the light will be red, if in position 1 the light will be yellow, and if in position 2 the light will be green.

In particular, when the second switch is moved to position 2 from the state 100, the light remains yellow.

            Gilles Feyrit noticed that there is a symmetry that allows us a more general conclusion.  What we have really shown is that as soon as we know two states that correspond to different colours and moreover, these states differ in the position of one switch while agreeing in the other two, then we know that the differing switch alone controls the colors.  For example, had we known only that 211 and 200 both corresponded to green, then we would have needed further information.  Likewise, being told that 211 is green while 110 is yellow would not be sufficient.  The statement of the problem by Alon et al. was yet more general.  It allows for any number of 3-position switches controlling the red-yellow-green colour of the traffic light.  You are told only that whenever the positions of all the switches are changed then the colour of the light changes; one can then prove that, in fact, the light is controlled by only one of the switches.  Apparently this was a problem of unknown origin that circulated in Hungary in the 1970s.