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.)

The following arrangements of flipped switches (1 = flipped, 0 = not flipped) will turn off the center light while keeping or returning off the other lights:

 0  0  0  1  1


 0  0  1  0  0


 0  1  1  0  1


 1  0  0  0  1


 1  0  1  1  0





 0  1  1  0  1


 1  0  0  0  1


 1  0  1  1  0


 0  0  1  0  0


 1  1  0  0  0





 1  0  1  1  0


 1  0  0  0  1


 0  1  1  0  1


 0  0  1  0  0


 0  0  0  1  1





 1  1  0  0  0


 0  0  1  0  0


 1  0  1  1  0


 1  0  0  0  1


 0  1  1  0  1

---------
Note that the center bulb has three neighbors flipped (counting itself and orthogonal neighbors but not diagonal), while each of the other bulbs has an even number (zero or two) counted the same way.

The program which found these is:
DECLARE SUB vary (r%, c%)
DEFINT A-Z
CLEAR , , 4000
DIM SHARED flip(6, 6)
DIM SHARED lit(6, 6)

lit(3, 3) = 1

vary 1, 1

END

SUB vary (r, c)
  IF r = 5 AND c = 5 THEN
   GOSUB checkIt
  ELSE
   IF c = 5 THEN r1 = r + 1: c1 = 1: ELSE c1 = c + 1: r1 = r
   vary r1, c1
  END IF
  flip(r, c) = 1 - flip(r, c)
  lit(r, c) = 1 - lit(r, c)
  lit(r - 1, c) = 1 - lit(r - 1, c)
  lit(r, c - 1) = 1 - lit(r, c - 1)
  lit(r + 1, c) = 1 - lit(r + 1, c)
  lit(r, c + 1) = 1 - lit(r, c + 1)
  IF r = 5 AND c = 5 THEN
   GOSUB checkIt
  ELSE
   IF c = 5 THEN r1 = r + 1: c1 = 1: ELSE c1 = c + 1: r1 = r
   vary r1, c1
  END IF
  flip(r, c) = 1 - flip(r, c)
  lit(r, c) = 1 - lit(r, c)
  lit(r - 1, c) = 1 - lit(r - 1, c)
  lit(r, c - 1) = 1 - lit(r, c - 1)
  lit(r + 1, c) = 1 - lit(r + 1, c)
  lit(r, c + 1) = 1 - lit(r, c + 1)
  EXIT SUB

checkIt:
  bad = 0
  FOR row = 1 TO 5
   FOR col = 1 TO 5
     IF lit(row, col) THEN bad = 1: EXIT FOR
   NEXT
   IF bad THEN EXIT FOR
  NEXT
  IF bad = 0 THEN
    FOR i = 1 TO 5
      FOR j = 1 TO 5
        PRINT flip(i, j);
      NEXT
      PRINT
    NEXT
    PRINT
  END IF
 RETURN

END SUB

Edited on November 2, 2003, 8:22 pm

Posted by Charlie on 2003-11-02 18:01:31