Finding minimum number of presses to shut down lamps

Question

I tried to solve a programming problem but my I was unable to see an efficient algorithm. Situation is like this: We have a set of n lamps which can be on (1) or off (0) like this: 1110001011101. That byte string means that there are 13 lamps forming a circle where first three lamps are on, then 3 next off and so on and circle mean that the last lamp is next to the first one.

Then we have been given an integer m>0. It means that in any turn we can choose a lamp and then it and its m adjacent lamps changes their state s to 1-s. I.e. if m=2 and lamp states are 1110001011101 then applying the process to the first lamp we get the sequence 0000001011110.

Now the question is that if the string of length about 2200 and m about 110 are fixed, how one can develop an algorithm that shut downs all the lamps with minimum number of turns?

Answer 1

This problem is similar to the well-known "lights out" problem. http://en.wikipedia.org/wiki/Lights_Out_%28game%29 One way to approach it is by using linear algebra. It's easier to understand with smaller numbers, say length = 5 and m = 1.

First note that choosing a lamp and changing it (and its neighbors') state twice has no effect. Second note that the order in which lamps (and their neighbors) are switch doesn't matter. So a strategy is just a set of lamps. We'll represent lamps that are chosen to be part of the strategy by 1 and lamps that are not chosen by 0. We place the 1's and 0's in a column vector, e.g., (0 1 1 0 1)^T where T is for transpose (rows become columns). That strategy means toggle the lamp in position 1 (starting at position 0, of course) and its two neighbors; then the lamp in position 2 and its two neighbors, and finally the lamp in position 4 and its two neighbors.

The effect of a strategy can be calculated by matrix multiplication over the field GF(2). GF(2) has just 2 elements, 0 and 1, with ordinary rules of arithmetic except for the rule 1 + 1 = 0. Then the effect of the strategy above is the result of matrix multiplication by a matrix with the result of choosing lamp i in the i-th column, in other words by a "circulant matrix` as follows:

[ 1 1 0 0 1 ] [0]   [0]
[ 1 1 1 0 0 ] [1]   [0]
[ 0 1 1 1 0 ] [1] = [0]
[ 0 0 1 1 1 ] [0]   [0]
[ 1 0 0 1 1 ] [1]   [1]

The result of the strategy (0 1 1 0 1)^T is to toggle only the light in the last position. So if you start with only the light in the last position lit, and apply the strategy, all the lights will be off.

In this simple case, we represent the initial configuration by a column vector b. The solution strategy is then a column vector x satisfying the matrix equation Ax = b.

The question now becomes, for given b, 1) is there an x satisfying Ax=b? 2) Is the solution x unique? If not, which x has the least 1's? 3) How can it be calculated?

The answers to the above questions will depend on the numbers "length" and "m" for the particular problem at hand. In the length = 5, m = 1 problem considered above, the theory of linear algebra tells us that there is a unique solution for any b. We can get solutions for b of the form (0 0 ... 1 ... 0)^T, in other words one 1 and the rest zero, by "rotating" the solution (0 1 1 0 1)^T. We can represent any solution uniquely as a linear combination of those solutions, so the strategy/solution with the minimum number of 1's is the same as the unique solution for any given initial state.

On the other hand, with length = 6 and m = 1, all three strategies (100100)^T, (010010)^T, and (001001)^T map to outcome (111111)^T, so that there is not a unique solution in some cases; by the theory of linear algebra, it follows that there is no solution in some other cases.

In general, we can tell whether solutions exist and are unique using Gaussian elimination. In the 5x5 case above, add row 0 to rows 1 and 4;

[ 1 1 0 0 1 ] [1 0 0 0 0]    [ 1 1 0 0 1 ] [1 0 0 0 0]
[ 1 1 1 0 0 ] [0 1 0 0 0]    [ 0 0 1 0 1 ] [1 1 0 0 0]
[ 0 1 1 1 0 ] [0 0 1 0 0] -> [ 0 1 1 1 0 ] [0 0 1 0 0] ->
[ 0 0 1 1 1 ] [0 0 0 1 0]    [ 0 0 1 1 1 ] [0 0 0 1 0]
[ 1 0 0 1 1 ] [0 0 0 0 1]    [ 0 1 0 1 0 ] [1 0 0 0 1]

then swap rows 1 and 2; then add row 1 to row 0 and row 4,

[ 1 1 0 0 1 ] [1 0 0 0 0]    [ 1 0 1 1 1 ] [1 0 1 0 0]
[ 0 1 1 1 0 ] [0 0 1 0 0]    [ 0 1 1 1 0 ] [0 0 1 0 0]
[ 0 0 1 0 1 ] [1 1 0 0 0] -> [ 0 0 1 0 1 ] [1 1 0 0 0] ->
[ 0 0 1 1 1 ] [0 0 0 1 0]    [ 0 0 1 1 1 ] [0 0 0 1 0]
[ 0 1 0 1 0 ] [1 0 0 0 1]    [ 0 0 1 0 0 ] [1 0 1 0 1]

then add row 2 to rows 0, 1, 3, 4; then add row 3 to rows 1, 2;

[ 1 0 0 1 0 ] [0 1 1 0 0]    [ 1 0 0 0 0 ] [1 0 1 1 0]
[ 0 1 0 1 1 ] [1 1 1 0 0]    [ 0 1 0 0 1 ] [0 0 1 1 0]
[ 0 0 1 0 1 ] [1 1 0 0 0] -> [ 0 0 1 0 1 ] [1 1 0 0 0] ->
[ 0 0 0 1 0 ] [1 1 0 1 0]    [ 0 0 0 1 0 ] [1 1 0 1 0]
[ 0 0 0 0 1 ] [0 1 1 0 1]    [ 0 0 0 0 1 ] [0 1 1 0 1]

and finally add row 4 to rows 1, 2:

[ 1 0 0 0 0 ] [1 0 1 1 0]
[ 0 1 0 0 0 ] [0 1 0 1 1]
[ 0 0 1 0 0 ] [1 0 1 0 1]
[ 0 0 0 1 0 ] [1 1 0 1 0]
[ 0 0 0 0 1 ] [0 1 1 0 1]

You can read off the basis of solutions in the columns of the right matrix. For example, the solution we used above is in the last column of the right matrix.

You should try Gaussian elimination in the length = 6, m = 1 case discussed above to see what happens.

In the given case (length = 2200, m = 110), I suspect that solutions always exist and are unique because the number of lamps toggled in one move is 221, which is relatively prime to 2200, but I suggest you use Gaussian elimination to find an explicit strategy for any starting position b. How would you minimize the number of moves if there were not a unique strategy?