Imagine there is a 5x5 grid of lights, and only the middle light in the grid is on.

The lights are wired such that when you flip the switch for one light (from on to off or off to on) the others right next to it (not diagonally) flip as well.

Using this weird wiring of lights, what is the fewest number of switch changes it takes to turn all the lights off, and which lights should you switch? (Assume all the switches work in the manner explained, and there is 1 switch for each of the lights.)

(In reply to Lights On! by wonshot)

To turn all the lights on from where only the center light was on would use the same sequence of moves as to turn all the lights off when all except the center light had been on. In order to do that, use the "Chase the lights" technique given in "real-world method" by Lee. I'll use this negative image here: all the lights are on except the middle and we want to get them all off, so as to match the terminology in Lee's post.

Every switch in the second row has to be flipped to turn out all the lights in the first row, as a result of this, only the first and last lights in that second row will remain (or again be) lit, and in the third row, only the center light will now be on, as the whole row has reversed. To get those two lights in the second row unlit, the first and last switches in the third row must be flipped, and this completely lights that third row while turning off the first and last lights in the fourth row. In order to turn off the lights in the third row, all the switches in the fourth row must be flipped. This also turns off all the bulbs in the fourth and fifth rows and all the lights are out. As all the lights are already out in the last row we need not continue with the method presented in Lee's post.

That means that in the puzzle posed now, starting with the negative of what we had here, all the lights would be on. And to recap: flip all the switches in the second and fourth rows, and only the first and last in the middle row.

By rotational symmetry it will also work with columns instead of rows.

But looking at my comment 22 (re (3); Brute Force), there are actually two other sets of XORs that will work to produce a total of four solutions:

 0  0  0  0  0


 1  1  1  1  1


 1  0  0  0  1


 1  1  1  1  1


 0  0  0  0  0





 0  1  1  1  0


 0  1  0  1  0


 0  1  0  1  0


 0  1  0  1  0


 0  1  1  1  0





 1  0  1  0  1


 0  1  0  1  0


 1  0  0  0  1


 0  1  0  1  0


 1  0  1  0  1





 1  1  0  1  1


 1  1  1  1  1


 0  1  0  1  0


 1  1  1  1  1


 1  1  0  1  1

-----------
where a 1 means to flip the switch and a zero means not to.

These results can also be produced by the program listed in Brute Force modified to start with all the lights lit except the center, rather than the negative of that.

Posted by Charlie on 2003-11-06 17:29:55