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:
+---+---+---+---+---+
| . | . | . | . | . |
+---+---+---+---+---+
| . | * | * | . | * |
+---+---+---+---+---+
| * | * | . | * | * |
+---+---+---+---+---+
| * | . | . | . | * |
+---+---+---+---+---+
| * | * | . | * | * |
+---+---+---+---+---+
Suppose you are handed a copy of this toy, with every square illuminated. Can you turn all the lights off?
Problem 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 may also affect the state of one or more other lights in the same way. Suppose that the switch to light relationship is symmetric, so that, if switch Si affects light Lj, then it is also true that Sj affects light Li. 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.
Back to the puzzle page.