PROBLEM LINKSDIFFICULTYHARD EXPLANATIONTo see how to solve this problem, let's take an example: 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 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 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 becomes 00000 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  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  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  Using Gauss elimination, this reduces to  1 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)}.
This question is marked "community wiki".
asked 28 Nov '12, 17:45
