A children's toy comprises a 5 by 5 grid of squares. Each square contains a light that can be turned on or off by pressing the square. However, when you press the square, you also affect the squares above, below, to the left and right of the square. Specifically, pressing a square reverses the state of the lights in that square and its 4 neighbors.
To identify a particular cell, we will use a letter. To indicate lights ON or OFF, we will use an asterisk or a period. Here is the starting position:
+---+---+---+---+---+
| A | B | C | D | E |
+---+---+---+---+---+
| F | G | H | I | J |
+---+---+---+---+---+
| K | L | M | N | O |
+---+---+---+---+---+
| P | Q | R | S | T |
+---+---+---+---+---+
| U | V | W | X | Y |
+---+---+---+---+---+
Here is what happens if you press the A, D and R
buttons:
+---+---+---+---+---+
| . | . | . | . | . |
+---+---+---+---+---+
| . | * | * | . | * |
+---+---+---+---+---+
| * | * | . | * | * |
+---+---+---+---+---+
| * | . | . | . | * |
+---+---+---+---+---+
| * | * | . | * | * |
+---+---+---+---+---+
Puzzle 1: Suppose you are handed a copy of this toy, with every square illuminated. Can you turn all the lights off?
Puzzle 2: Suppose we have a set of N lights Li and switches, Si. Suppose that switch Si always reverses the state of light Li, and there may be some other set of lights whose state it also always reverses. Moreover, suppose that the relationship between switches and lights is symmetric, that is, if switch Si affects light Lj, then it is also true that switch Sj affects light Li.
This abstract language may throw you off, but note that these statements are true about the toy in problem 1. Each box is both a switch we can depress and a light that goes on and off. In the toy, pressing the switch reverses the corresponding light, and the four neighbors, and each of those neighbors can also affect the given light in the same way. Now we're just saying, suppose that the lights controlled by each switch are now scattered around in a more arbitrary way.
Using only these assumptions, show that, if all the lights are initially on, it is always possible to operate the switches in such a way that all the lights are off.
I give up, show me the solution.