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 Brute Force by Charlie)

As Charlie have shown, there are exactly four solutions to this problem, all rotations of each other. As I have said earlier, there are 2^25 combinations of lights possible using this wiring system, and some of the combinations may be the same. There are also 2^25 combinations on a normally wired grid of lights. This program showed that at least 3 of the possible flipping combinations have the same effect as other combinations. Therefore, certain combinations of switched lights must be impossible, at least three, and probably more. I wonder what they are.

Posted by Tristan on 2003-11-03 18:58:17