PROBLEM LINKS
DIFFICULTY
HARD
EXPLANATION
To see how to solve this problem, let’s take an example:
5 3
10100
01100
10011
00010
00100
3 5
5 1
5 3
First, let’s pretend all lights can be pressed.
Note that the order in which the lights are pressed doesn’t matter, and pressing a light twice is the same as not pressing it at all. Therefore a solution consists of a set of lights.
A solution is determined by which lights in the top row are pressed: Since the order doesn’t matter, we can press those first, and then “chase the lights”: For every light in the top row that is on, we have to press the light below it, and we can’t press any other lights in the second row. Then, for every light in the second row that is on, we have to press the light below it. The same for the third row, and so on.
If we press lights on the top row, not corresponding to a solution, and then chase the lights, only the bottom row will have lights on. What’s more, the effect of pushing some lights at the top, say k of them, and chasing the lights, then pressing another light at
the top and chasing the lights again, is the same as first pressing all k+1 lights (some of them possibly the same) and then chasing the lights. Also, whether a light is pressed an odd or even number of times doesn’t change.
To solve the puzzle, first chase the lights, to reduce the problem to the case where only the bottom row has any lights on. In our example, we get
00000
00000
00000
00000
10001
Now, for each light on the top row, start with all lights off, press that light, chase the lights, and see what the effect on the bottom row is. For instance
11000
10000
00000
00000
00000
becomes
00000
00000
00000
00000
01101
So, pressing (1,1) and chasing the lights will toggle lights 2, 3 and 5 on the bottom row. We want a set of lights in the top row, such that the combined effect on the bottom row is to toggle lights 1 and 5. In other words we have to solve five equations in five unknowns, where arithmetic is performed modulo 2. In Matrix notation: Ax=b, where:
| 0 1 1 0 1 | | 1 |
| 1 1 1 0 0 | | 0 |
A = | 1 1 0 1 1 | and b = | 0 |
| 0 0 1 1 1 | | 0 |
| 1 0 1 1 0 | | 1 |
Column j of A is the bottom row after pressing (1,j) on a blank grid and chasing the lights. b is the bottom row after chasing the lights in the original configuration.
But some lights can’t be pressed. This adds some additional constraints to the system of equations. Starting with a blank grid, pressing one button at the top, and chasing the lights, we look at which faulty lights are pressed in the process. For instance, starting with (1,1), no faulty lights are pressed. Starting with (1,3), we press (3,5) and (5,3). Going through all five lights at the top, we have the constraints
| 0 0 1 0 1 | | 0 |
| 0 0 0 0 1 | x = | 1 |
| 0 0 1 0 0 | | 1 |
The rows correspond to (3,5), (5,1) and (5,3), in that order. The column on the right corresponds to faulty buttons that are pressed in the first step of the solution, when we chase the lights to clear everything except the last row. Putting these equations together, we must solve
| 0 1 1 0 1 | | 1 |
| 1 1 1 0 0 | | 0 |
| 1 1 0 1 1 | | 0 |
| 0 0 1 1 1 | x = | 0 |
| 1 0 1 1 0 | | 1 |
| 0 0 1 0 1 | | 0 |
| 0 0 0 0 1 | | 1 |
| 0 0 1 0 0 | | 1 |
Using Gauss elimination, this reduces to
| 1 0 0 0 0 | | 0 |
| 0 1 0 0 0 | | 1 |
| 0 0 1 0 0 | | 1 |
| 0 0 0 1 0 | x = | 0 |
| 0 0 0 0 1 | | 1 |
| 0 0 0 0 0 | | 0 |
| 0 0 0 0 0 | | 0 |
| 0 0 0 0 0 | | 0 |
So there is a unique solution, which is to press lights 2, 3, and 5 in the top row, and chase the lights, giving the solution set {(1,2),(1,3),(1,5),(2,3),(2,5),(3,2),(3,3),(4,3)}.