Turn Out the Lights (07/13/2002)



Prepared by:

Joseph Malkevitch
Mathematics and Computing Department
York College (CUNY)
Jamaica, NY 11451

Email: malkevitch@york.cuny.edu (for additions, suggestions, and corrections)




In the Summer 2000 issue (Volume 22, number 3) of the Mathematics Intelligence (Springer-Verlag) Alexander Shen writes about a fascinating puzzle (pgs. 20-21) which he first heard about from Michael Sipser (MIT).

Imagine that one has an mxn rectangle array. Think of each cell in the array as being a switch that turns on or off the light in that cell of the array.

Whenever one touches a cell of the array it changes the state of that cell (either from on to off or off to on) as well as the neighbors of that cell as a chess rook would move. Thus, for example if one touches the cell (2,2) in the 3x3 array in which all the lights of the cells are off except the cell (2,2) then the result would be that (2,2) would turn off and cells (1,2), (2,1), (2,3) and (3,2) would be turned on. Touching a cell sometimes affects 5 lamps, sometimes 4 lamps, and for the four corners of the array only three lamps.

Puzzle:

Show that for any mxn rectangular array there is always a sequence of moves that takes the completely lit array and after the sequence of moves all the lights are turned out.

Remark:

One can think of this puzzle as a kind of solitaire being played on the graph consisting of the dots at the centers of the cells in the mxn array and with edges that represent the adjacency of the cells (under chess king moves).

Shen gives a proof which uses linear algebra that this can always solve the puzzle and reports on extending the game to arbitrary graphs. He also discusses solutions that do not use linear algebra.

The following issues (not raised by Shen) would also seem to be of interest:

1. Let f(m,n) be the minimum number of moves needed to turn out the lights starting with a totally lit mxn array. Compute the values of f(m,n). Also, are their patterns of on and off states of the cells that can not be reached from the initial state of all cells on? (In graph theory terms is the state space of configurations connected?)

2. Turn the (solitaire) puzzle above into a 2 person game as follows. Suppose we have player A and player B who alternate moves. A's goal is finish with all the lights on and B's goal is to finish with all the lights off. A moves first (thereby turning some cells off). We impose one additional rule: either player can not move at the cell that his/her opponent chose on the previous move.

a. Can this game always be played to a draw?

b. If there are values of m and n which can not always be played to a draw, what are these values?

c. What graphs, if any, can be played on so that a draw can not be forced?







Back to list of tidbits