How to find a minimum number of switch presses to shut down all lamps?

edit

[Note that i started to write my answer before the numbers changed, so let me start with 2107 lamps and then deal with the 120 lamps]

First, it should be clear that testing all the $2^{2107}$ possibilities is not possible, so brute force (which is the first technique to be considered) is not an option.

The situation you describe can be modeled as follows:

• the pressing of some of the 2107 lamps (viewed as interrupters) can be seen as a vecror $I$ in $F^d$, where $F$ is the finite field with two elements (a 1 at position i tells that the interrupter i is pressed).

• the state of the 2107 lamps can also be seen as a vecror $L$ in $F^d$ (a 1 at position i tells that the lamp i is turned on).

The situation you describe is linear: if we start from a completely off position (zero vector), if we press the interrupters encoded as a vector $I$, we get some lamps turned on as a vector $L$ with the following relation: $L=M*I$, where $M$ is the matrix over $F$ where $M_{i,j}=1$ iff $j$ is between $i-108$ and $i+108$ (zero otherwise), where indices have to be understood modulo 2107.

In your question, you start with some lamps open (represented by a vector $L_{init}$) and want to press some interuptors in order to turn them all off. So, you want to find a pressing of interruptors $I$ such that $ L_{init}+MI = 0 $ This is equivalent to $ MI = L_{init} $ (remember that in $F$ we have $1=-1$).

Here is a way to encode the situation in Sage (the input is given as a string of 0's and 1's):

sage: input = '0111110100011000011111101110010101100011100111101110100100111011111000110001100110010101001010111011010010000101111111111001101010111011110100100101000101100011111010001001001010111010000011110010100001111010111111000100101100001001101001000100110101110010110011110010101101100111111001001100011011011101011001010010111001111111011100001110011111001000100100011010110011000101100111111001011110101110011101011011111011010100010110010001100010110000110111100011111001101000101001011101111100110011001110010010001010101111100000100100011001111001001101110111010010111111001100100110000101100101101010100110101000011011110001010000010001000110100111010100100111011011111101001101011111110110010001101110010000111011011100010000011111101000010101011111011011000011111100000001110001001101100101100011010111010111111000011000101100101100110000000001001111100101110100100011011010011100000000111101010100011101100011011010000110101100111001101110101111101100000100001000101001111001000110000101010000010111101110000100011000110001000000101110111010011111101000100100000110001001010101011001001001110110101000001001001100001011001101110001111110011100111010110111000101110100000100111101100110110000111010011111011010010000101111000010000001100110100101110100100001010100100101111111101110001110001000011011001011101000111111001011001111101111110110101111101111011111100111110011010111010111111001001010110111111111110001001001111000111011101101000100011011001010110100101101000000110010001001000100111011010001111110001111110101001101111011010101010101001101100110110001111111000100000111011010101011000010001101111011011011010001100110111100100010000000111100111001111000000010100100111000011101111100000101010101010010100101101000101101010001101100111011001010000010001111011110000101111111010101101101110110001111100011001110000100100101001111000011111110001001100101000001011011100010001101100010000011001100000010110000101000101101110000101100100010101111100011100001001011110100001000011001101000000100100011000010000011001101111101001001111001100110001000100101011111001011001111110001011111001101010101001'

sage: d = 2107
sage: m = 108
sage: F = GF(2)

sage: L_init = vector(F,input)

sage: M = matrix(F,d,d)
....: for i in range(d):
....:     for j in range(-m,m+1):
....:         M[i,(i+j) % d] = 1

sage: M
2107 x 2107 dense matrix over Finite Field of size 2 (use the '.str()' method to see the entries)

We get a solution of the problem by solving the equation $M*I = L_{init}$:

sage: I = M.solve_right(L_init)

We can see that this particular solution has 1035 solutions

sage: len(I.nonzero_positions())
1035

But there might be better solutions. The set of solutions is an affine space, a classical way to find small vectors where the base ring is $\mathbb{Z}$ is with lattice reduction. Integer linear programming can be used too. But here (where we have cancellations $1+1=0$), it seems hard to use.

Since we are in a linear situation, the set of solitions can be easily described as $I+K$, where $K$ is the kernel of $M$: indeed $S$ is a solution iff $ MS=L_{init} $ iff $M(S+I)=0$ iff $S+I\in Ker(M)$.

Let us look at that kernel:

sage: K = M.right_kernel() ; K
Vector space of degree 2107 and dimension 6 over Finite Field of size 2
Basis matrix:
6 x 2107 dense matrix over Finite Field of size 2

It has dimension 6, so the number of solutions is $2^6$, which is much smaller than $2^{2107}$. So, here we, can consider brute force to conclude: it suffice to look at the number of pressed interrupters for all the solutions and take the minimum:

sage: min([len((I+k).nonzero_positions()) for k in K])
1007

So, the minimum number of turns to shut off all lamps is 1007.

For the smaller problem, it suffice to do the same:

sage: input = '101011011000010000010101100101111101011110100111010011000000100010100110101100000000100110010100010010110111000000010110'
sage: F = GF(2)
sage: L_init = vector(F,input)
sage: d = len(L_init)
sage: m = 7
sage: M = matrix(F,d,d)
....: for i in range(d):
....:     for j in range(-m,m+1):
....:         M[i,(i+j) % d] = 1
sage: I = M.solve_right(L_init)
sage: K = M.right_kernel() ; K.dimension()
14
sage: min([len((I+k).nonzero_positions()) for k in K])
46

So, the minimum number of turns to shut off all lamps is 46.

Note that this problem is actually harder sinc Sage has to test $2^{14}=16384$ solutions.

SOLVED

(...had to solve it with the own devices, the source of the problems was not helpful, neither was the link to Art of Problem Solving (which should have been rather done of the sister site Start of Problem Solving).)

EDITED ANSWER:

For the reader in hurry and only the solution, please go directly to the string final solution below. (The already typed code still remains, since it shows the trials and errors on the road. They support the solution, and document somehow the search. It also remains because of my experience with maths books that give only the cosmetic last mirror of a solution on minimum of space. This was the reason to have a hard time with simple structures that are best understood by examples.)

The first post was given with $N=2107=7^2\cdot 43$, and there were $M=108+1+108=317=7\cdot31$ consecutive lamps to be changed in the same time.

Then we finally have more posted cases to test the code, and even the source. This is here and generally very helpful! The mathematical model is as follows.

• Let $F=\mathbb F_2$ be the field with two elements.
• Let $N=120$, and let $V=F^N$ be the vector space over $F$ of dimension $N$.
• On $V$ we have a canonical basis, the vectors $v_j$ with components $(\dots,0,0,1,0,0,\dots)$, where the one is on position $j$.
• Let $m=7$. We define now an other system of vectors, $w_j$, where $w_j$ has the components on positions $j-m, \dots,j,\dots,j+m$ equal to one, else zero on the other components. Indices are taken modulo $N$, and we prefer to use $0,1,\dots,(N-1)$ for the representatives of the classes modulo $N$. It is also simpler to implement it in python. So there are $M=2m+1$ components equal to one in each of the vectors.
• The first question is, if $w_0,w_1,\dots$ form a generating system for $V$. We will always display vectors as column vectors. We compute the determinant of the matrix

$$ A = [\; w_0\; w_1\; w_2\; \dots\; ] $$

• For this, we replace the "zeroth" column $w_0$ with $w_0-w_1$, get a matrix with the same determinant, then column $w_1$ with $w_1-w_2$, and so on. The forelast columns still can be changed, using the last one. But the last one remains. We get a matrix

$$\det A =\det[\; (w_0-w_1)\; (w_1-w_2)\; (w_2-w_3)\; \dots\; (w_{N-2}-w_{N-1})\; w_{N-1}\;]\ .$$

• Note that all resulted columns have exactly two entries equal to $1$, all but the last one.
• Now we replace one of the lines by the sum of all lines.

Let us write code for this. It is better to use $M=2m+1$ in code for the number of consecutive entries $=1$ in each column.

def A( N, M ):
    F = GF(2)
    R = range(N)

    lists_for_M = [ [ (j+k) % N for k in range(M) ]
                    for j in R ]
    return matrix( F, N, N, [ [ F(1) if k in lists_for_M[j]
                                else F(0)
                                for k in R ]
                              for j in R ] ).transpose()
print A( 12, 5 )
print "The determinant of the above matrix is:"
print A( 12, 5 ).det()

And we get:

[1 0 0 0 0 0 0 0 1 1 1 1]
[1 1 0 0 0 0 0 0 0 1 1 1]
[1 1 1 0 0 0 0 0 0 0 1 1]
[1 1 1 1 0 0 0 0 0 0 0 1]
[1 1 1 1 1 0 0 0 0 0 0 0]
[0 1 1 1 1 1 0 0 0 0 0 0]
[0 0 1 1 1 1 1 0 0 0 0 0]
[0 0 0 1 1 1 1 1 0 0 0 0]
[0 0 0 0 1 1 1 1 1 0 0 0]
[0 0 0 0 0 1 1 1 1 1 0 0]
[0 0 0 0 0 0 1 1 1 1 1 0]
[0 0 0 0 0 0 0 1 1 1 1 1]
The determinant of the above matrix is:
1

(This may seem irrelevant. Then please skip. But there is some structure, it is maybe important to look for the kernel. Here, computing the determinant, we get some feeling about the possible column relations.) For A( 120, 15 ) the det is zero. Our strategy to compute the determinant, was to replace the above matrix with other matrices with same determinant:

sage: A0 = A(12, 5 )
sage: A0.add_multiple_of_column( 0,1,1 )
sage: A0
[1 0 0 0 0 0 0 0 1 1 1 1]
[0 1 0 0 0 0 0 0 0 1 1 1]
[0 1 1 0 0 0 0 0 0 0 1 1]
[0 1 1 1 0 0 0 0 0 0 0 1]
[0 1 1 1 1 0 0 0 0 0 0 0]
[1 1 1 1 1 1 0 0 0 0 0 0]
[0 0 1 1 1 1 1 0 0 0 0 0]
[0 0 0 1 1 1 1 1 0 0 0 0]
[0 0 0 0 1 1 1 1 1 0 0 0]
[0 0 0 0 0 1 1 1 1 1 0 0]
[0 0 0 0 0 0 1 1 1 1 1 0]
[0 0 0 0 0 0 0 1 1 1 1 1]
sage: A0.add_multiple_of_column( 1,2,1 )
sage: A0
[1 0 0 0 0 0 0 0 1 1 1 1]
[0 1 0 0 0 0 0 0 0 1 1 1]
[0 0 1 0 0 0 0 0 0 0 1 1]
[0 0 1 1 0 0 0 0 0 0 0 1]
[0 0 1 1 1 0 0 0 0 0 0 0]
[1 0 1 1 1 1 0 0 0 0 0 0]
[0 1 1 1 1 1 1 0 0 0 0 0]
[0 0 0 1 1 1 1 1 0 0 0 0]
[0 0 0 0 1 1 1 1 1 0 0 0]
[0 0 0 0 0 1 1 1 1 1 0 0]
[0 0 0 0 0 0 1 1 1 1 1 0]
[0 0 0 0 0 0 0 1 1 1 1 1]

If we perform all operations, then we get finally:

A0 = A( 12, 5 )
for j in range( 11 ):
    A0.add_multiple_of_column( j, j+1, 1 )

and we get:

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

Now we add all rows to the last one. The last row will have only one entry equal to $1$, the diagonal one, we can expand using Leibniz rule for it, and get the minor obtained by removing the last row, and the last column.

Now we start a process of deleting rows and columns for the last removed $1$ entries (in the last removed lines and columns).

Let us stop here. At any rate, we get a zero determinant in case we have a common divisor of $M$ and $N$. (One direction is easy to show.)

Back to our problem. We have to deal with the matrix

sage: A( 120, 15 )
120 x 120 dense matrix over Finite Field of size 2 (use the '.str()' method to see the entries)
sage: A( 120, 15 ).det()
0
sage: A( 120, 15 ).rank()
106

of rank $106$. First of all, let us see if the given vector is in the vector space spanned by the columns of $A$.

N = 120
STR ="""
1010110110000100000101011001011111010111
1010011101001100000010001010011010110000
0000100110010100010010110111000000010110"""

A0 = A( 120, 15 )
v = matrix( F, N, 1, [ F(int(s)) for s in STR if s in '01' ] )
B = block_matrix( 1, 2, [ A0, v ] )
print "The rank of the extended matrix is %s" % B.rank()

OK, we get:

The rank of the extended matrix is 106

Then we need a solution, any particular one. Here is it:

sage: w0 = A0.solve_right(v)
sage: A0*w0 == v
True

(There is no place here to show all $N=120$ components of it.)

Any other solution of the same equation is of the form $w_0+u$, where $u$ is an element in the kernel of the matrix A0 = A( 120, 15 ).

This kernel has dimension equal to gcd( M, N ) - 1, which is in our case

sage: A0.kernel().dimension()
14

This is a space of dimension $14$, and there are $2^{14}$ vectors in it. This is rather a small number. We can iterate through it, for each of the $2^{14}$ vectors of shape $w_0+u$ we record the number of the "lamp operation" needed, i.e. the number of entries equal to $1$, and search for the one, for some vector where the minimum is reached.

The code would be:

N = 120
STR ="""
1010110110000100000101011001011111010111
1010011101001100000010001010011010110000
0000100110010100010010110111000000010110"""

A0 = A( 120, 15 )
v  = matrix( F, N, 1, [ F(int(s)) for s in STR if s in '01' ] )
w0 = vector( A0.solve_right( v ) )


def getString( vec, breakLength=40 ):
    # s = ''.join( [ str(entry) for entry in vec ] )
    s = ''
    for count in range( len( vec ) ):
        s += str( vec[count] )
        if  (count+1) % breakLength == 0 and count < len(vec)-1 :
            s += '\n'
    return s

minOperations = N+1    # default, it will become smaller soon
solution = None        # we change it, finally it will be the solution
for u in A0.kernel():
    vec = u + w0
    nrOperations = len( vec.nonzero_positions() )
    if nrOperations < minOperations:
        minOperations = nrOperations
        solution      = vec
        print "New minOperations %s for\n%s\n" % ( minOperations, getString(vec) )

print "MINIMAL NUMBER OF OPERATIONS = %s" % minOperations
print "SOLUTION IS:\n%s" % getString( solution )

# we can search for all solutions
print "ALL SOLUTIONS:\n"
for u in A0.kernel():
    vec = u + w0
    if minOperations == len( vec.nonzero_positions() ):
        print getString( vec )
        print

It gives:

New minOperations 60 for
1111101101000111111010011101001111101111
1101001100110101101010101001111010111101
0011000000100100000011101000000000000000

New minOperations 58 for
0111101101000100111010011101010111101111
1101111100110101101100101001111010001101
0011000001000100000011100100000000000001

New minOperations 54 for
0011101101000110011010011101000011101111
1101010100110101101001101001111010100101
0011000000010100000011101110000000000000

New minOperations 52 for
0101101101000110101010011101000101101111
1101011000110101101000001001111010101001
0011000000001100000011101101000000000000

New minOperations 50 for
0000101101000110000010011101000000101111
1101010010110101101001011001111010100011
0011000000011000000011101111100000000000

New minOperations 48 for
0001101111000110001010001101000001101101
1101010000110001101001001001011010100001
0010000000011100001011101111000001000000

New minOperations 46 for
0000101111100110000010001001000000101101
0101010010110000101001011001010010100011
0010010000011000001001101111100001010000

MINIMAL NUMBER OF OPERATIONS = 46
SOLUTION IS:
0000101111100110000010001001000000101101
0101010010110000101001011001010010100011
0010010000011000001001101111100001010000
ALL SOLUTIONS:

0000101111100110000010001001000000101101
0101010010110000101001011001010010100011
0010010000011000001001101111100001010000

0001001111100110001110001001000001001101
0101010001110000101001000001010010100000
0010010000011110001001101111010001010000

0001101011100110001010101001000001101001
0101010000111000101001001000010010100001
0000010000011100011001101111000011010000

0000001011100110000110101001000000001001
0101010011111000101001010000010010100010
0000010000011010011001101111110011010000

0001101110100110001010000001000001101100
0101010000110010101001001001000010100001
0010110000011100001101101111000001110000

0000001110100110000110000001000000001100
0101010011110010101001010001000010100010
0010110000011010001101101111110001110000

0000101010100110000010100001000000101000
0101010010111010101001011000000010100011
0000110000011000011101101111100011110000

0001001010100110001110100001000001001000
0101010001111010101001000000000010100000
0000110000011110011101101111010011110000

A last check:

sage: A0 * matrix( F, N, 1, list(solution) ) == v 
True

It is possible, that something went wrong on the road. But the principle is simple, we need one special solution, then generating elements of the kernel of the corresponding lamp matrix, the kernel should have a small dimension, we loop, for each element in the kernel, solution of the homogenous system for the kenel matrix, we associate a solution of the inhomogenous system for the lamp matrix and the state that should be reached. The problem wants the vector in this space which has a minimal amount of nonzero entries. (This is of course a human, non-structural requirement. For a structural question i would have invested more effort, so that the code should have worked also for "bigger" kernels.)

Note:

To "see" the kernel, and imagine how would it look like "in general", try:

sage: print K.matrix().transpose().str()

(Then complete the proof about the rank of the matrix...)

New edit after seeing the new cases and the new problems The above discussion was only searching for the optimal number of switches, i had no idea that we need an algorithm for the whole industry of cases...

I'll post some working code, but it works of course with limitations, let us have the code and its output, then the limitations are clear:

# # # PUTTING ALL IN ONE...
F = GF(2)

def getA( N, M ):
    R = range(N)
    lists_for_M = [ [ (j+k) % N for k in range(M) ]
                    for j in R ]
    return matrix( F, N, N, [ [ F(1) if k in lists_for_M[j]
                                else F(0)
                                for k in R ]
                              for j in R ] ).transpose()

def getString( vec, breakLength=80 ):
    # s = ''.join( [ str(entry) for entry in vec ] )
    s = ''
    for count in range( len( vec ) ):
        s += str( vec[count] )
        if  (count+1) % breakLength == 0 and count < len(vec)-1 :
            s += '\n'
    return s

CASES = (
    ( 6, 1, '101101' ),
    ( 10, 2, '1011010110' ),
    ( 20, 1, '11111011101010111111' ),
    ( 30, 7, '011100001010011011100001010011' ),
    ( 39, 6, '110100111111101000011000100110111100010' ),
    ( 53, 9,
      '''0101100101111100100011100111101001001010
      0010000010110''' ),
    ( 120, 7,
      '''1010110110000100000101011001011111010111
      1010011101001100000010001010011010110000
      0000100110010100010010110111000000010110''' ),
    ( 220, 27,
      '''1110111111101000100110011001100110100000
      0010100011000111101100111111000001010000
      1010110110011100100010011011010111100011
      0101101000010000100110111101001001011010
      1101001001110110001100011010111101001100
      11010111110101010100''' ),
    ( 500, 87,
      '''1010001101101001110001101001000101010100
      0001111111001101011000000011001111111011
      1001110011010111111011010100010011011001
      1001101110011011100001000111110101011111
      1100111100001100110011101110101100001111
      1100010010011010001111000000101110101101
      1010100001100011111000111001000101101000
      1011111111101111000000011111010001000000
      1110011110111101010010011000000100010100
      0011101011010011010110011110111000010010
      0111100100011010010110001000011100101001
      1110111010001001011001111011111011010110
      10101101111011101110''' ),
    ( 1002, 83,
      '''0010100100100101000000110101111111101011
      1101000101111110001110000110110110010101
      1110110011011101100110111001110110010011
      1101111010110011110101100001101010100011
      1110001100011111110100011110100111111100
      0011001011100110101100001101000001110010
      0110100000100100100000011010000010111100
      1110001110011110101001100111101101010000
      0101010000011010011110101001001001000000
      0011000100011011011001111010001101111000
      0100001011010011001010111001111100110001
      0011111110101101001100111101110000000000
      1101100100000011000010010100010101001000
      1100001000101001100110010100001000001101
      1101000100001010011000101001101000100010
      0011010001011101010100011101001101101100
      0111110100110011001111000000001001001001
      1001111001011111000010110000110010101000
      1011001100111101000101000110000111010100
      0010011011010111001101011001111000001011
      1110101010101101111011111110100001100110
      1000101100110011010000110000011011110011
      0010000010000000111101101000001111101111
      0100111110010101100011101001111101010000
      1111100010011001110111111000101000000101
      01''' )
)

def info( N, M, lamps ):
    d = gcd( M, len(lamps) )
    print "N=%s :: The vector space has dim = 2**(%s-1) = %s" % ( N, d, 2**(d-1) )
    return 2**(d-1)

def search( M, lampsVector, verbose=False ):
    N = len( lampsVector )
    A = getA( N, M )
    v = matrix( F, N, 1, lampsVector )
    w = A.solve_right(v)

    if verbose:
        print "possible switches (maybe not minimal):\n%s" % getString( vector(w) )
        print "kernel vectors that can be used:"
        for u in A.kernel().basis():    print getString(u)

    minOperations = N+1
    solution = None

    for u in A.kernel():
        vec = u + vector(w)
        nrOperations = len( vec.nonzero_positions() )
        if nrOperations < minOperations:
            minOperations = nrOperations
            solution      = vec
            if verbose:
                print "New minOperations %s for\n%s\n" % ( minOperations, getString(vec) )

    # print "Minimal number of operations is %s" % minOperations
    return minOperations, solution

for N, m, case in CASES:
    M = 2*m+1
    lamps = [ F(int(s)) for s in case if s in '01' ]
    if N != len(lamps):
        print "Invalidated case: N=%s" % N
        continue
    # else:
    if info( N, M, lamps ) > 10000:
        print "*** Too many cases, an other algorithm is needed...\n"
        continue

    nr, solution = search( M, lamps )
    print ( "N=%s M=%s SOLUTION: %s switches as follows:\n%s\n\n"
            % ( N, M, nr, getString( solution ) ) )

This delivers:

N=6 :: The vector space has dim = 2**(3-1) = 4
N=6 M=3 SOLUTION: 2 switches as follows:
010001


N=10 :: The vector space has dim = 2**(5-1) = 16
N=10 M=5 SOLUTION: 4 switches as follows:
1110100000


N=20 :: The vector space has dim = 2**(1-1) = 1
N=20 M=3 SOLUTION: 8 switches as follows:
10010100111000100100


N=30 :: The vector space has dim = 2**(15-1) = 16384
*** Too many cases, an other algorithm is needed...

N=39 :: The vector space has dim = 2**(13-1) = 4096
N=39 M=13 SOLUTION: 9 switches as follows:
101000100000001000000100110001100000000


N=53 :: The vector space has dim = 2**(1-1) = 1
N=53 M=19 SOLUTION: 25 switches as follows:
11110010100010100111011100010110001000011101001000101


N=120 :: The vector space has dim = 2**(15-1) = 16384
*** Too many cases, an other algorithm is needed...

N=220 :: The vector space has dim = 2**(55-1) = 18014398509481984
*** Too many cases, an other algorithm is needed...

N=500 :: The vector space has dim = 2**(25-1) = 16777216
*** Too many cases, an other algorithm is needed...

N=1002 :: The vector space has dim = 2**(167-1) = 93536104789177786765035829293842113257979682750464
*** Too many cases, an other algorithm is needed...

So we really need to improve the search. How? Let us consider:

sage: N, m, c = CASES[4]
sage: search( 2*m+1, [ F(int(s)) for s in c if s in '01' ], verbose=1 )
possible switches (maybe not minimal):
101110100000001011000100110000000000000
kernel vectors that can be used:
100000000000110000000000011000000000001
010000000000101000000000010100000000001
001000000000100100000000010010000000001
000100000000100010000000010001000000001
000010000000100001000000010000100000001
000001000000100000100000010000010000001
000000100000100000010000010000001000001
000000010000100000001000010000000100001
000000001000100000000100010000000010001
000000000100100000000010010000000001001
000000000010100000000001010000000000101
000000000001100000000000110000000000011
New minOperations 11 for
101110100000001011000100110000000000000

New minOperations 9 for
101000100000001000000100110001100000000

So we get a particular solution, need then its minimal distance to some (linear) code... I think i have to come back...

Continuation

The algorithm described by example

Let us consider the particular solution of the inhomogenous system from above:

New minOperations 11 for
101110100000001011000100110000000000000

In our case, the key invariant is $d$, the gcd for $N$ and $M=2m+1$. The dimension of the kernel of $A$ is $d-1$, and the simplest way to describe the kernel is as follows.

Let us consider the vectors having $N/d$ components equal to $1$, all of them placed at same cyclic distance from each other. In our case, we may take the rows in

100000000000010000000000001000000000000
010000000000001000000000000100000000000
001000000000000100000000000010000000000
000100000000000010000000000001000000000
000010000000000001000000000000100000000
000001000000000000100000000000010000000
000000100000000000010000000000001000000
000000010000000000001000000000000100000
000000001000000000000100000000000010000
000000000100000000000010000000000001000
000000000010000000000001000000000000100
000000000001000000000000100000000000010
000000000000100000000000010000000000001

These rows are not in the kernel, but the difference (or the sum in characteristic two) of any two of them is in the kernel. So we may use such differences to "move lamps switch solutions" from one solution to the other one, hoping for a progress in reducing the number of the one entries used.

For this purpose, let us start with a particular solution, the above one:

101110100000001011000100110000000000000

We define its pattern as an element in $$\mathbb Z_{\ge 0}^d$$ as follows. We split it in groups of $d$ digits:

1011101000000 0101100010011 0000000000000

We put the groups in a table:

1011101000000
0101100010011
0000000000000

Then we count the number of ones in each column, getting the pattern

1112201010011

We then immediately detect the two positions with 22 as suboptimal, and use the one against the other one to reduce the number of operations. We explicitly use the difference of the two vectors

0001000000000 0001000000000 0001000000000
0000100000000 0000100000000 0000100000000

So that the new pattern is

1111101010011

and we cannot exploit any other situation. An other example is the one with $(N,m,M,d)=(120,7,15,15)$. We obtained a particular solution with a total of $60$ "switch operations". This was:

111110110100011
111101001110100
111110111111010
011001101011010
101010011110101
111010011000000
100100000011101
000000000000000

656442345453333

Its pattern was displayed below the $d$--groups. I am editing here with bare hands. Let me check that we get that \verb+60+:

sage: sum( [ int(s) for s in '656442345453333' ] )
60

Now we immediately see the problematic columns. The 6 on the first place can be exchanged (against some other column(s)) to its opposite. We can use the other 6 for this purpose. Also, the appearences of 5 are not welcome, everything strictly bigger than the half of the column length, $4$ in our case, is not welcome. So, applying simplifications with vectors in the kernel of the matrix A we can successively reduce then number of switches as follows:

656442345453333
6 6                   66 replaced with 22
252442345453333
 5      5             55 replaced with 33
232442343453333
         45           45 replaced with 43
232442343433333

And there is no progress any longer. Of course, we can "exchange an even number of 4, passing to the complementary 4", the relevant positions are

232442343433333
   **  * *

this is the reason for the numerous, i.e. 2^(4-1) solutions. Let us write code that finds the pattern.

def pattern( d, solution, verbose=False ):
    # d must divide the lenght of solution
    n = len( solution )
    if n % d:
        return
    blocks = [ [ solution[ j + d*k ] for j in range(d) ]
               for k in range(n/d) ]
    if verbose:
        for block in blocks:
            print ''.join( [ str(b) for b in block ] )

    if type( solution ) == str:
        return [ sum( [ 1 for block in blocks if int( block[k] ) ] )
                 for k in range(d) ]

    return [ sum( [ 1 for block in blocks if block[k] ] )
             for k in range(d) ]

Then we have for the one particular, not optimal solution the following pattern:

bad = """
    111110110100011
    111101001110100
    111110111111010
    011001101011010
    101010011110101
    111010011000000
    100100000011101
    000000000000000"""
sol = """
    000010111110011
    000001000100100
    000010110101010
    100101100001010
    010110010100101
    000110010010000
    011000001001101
    111100001010000"""

bad = ''.join( [ s for s in bad if s in '01' ] )
sol = ''.join( [ s for s in sol if s in '01' ] )

d = 15
print pattern( d, bad )
print pattern( d, sol )

This gives:

[6, 5, 6, 4, 4, 2, 3, 4, 5, 4, 5, 3, 3, 3, 3]
[2, 3, 2, 4, 4, 2, 3, 4, 3, 4, 3, 3, 3, 3, 3]

One can also observe exactly what happens by comparing the columns in bad (a non optimal lamps switch operations), and sol (an optimal solution).

From this, we have only to write the algorithm that performs the search. Sage will do it quickly for all cases.

FINAL SOLUTION

F = GF(2)

CASES = (
    ( 6, 1, '101101' ),
    ( 10, 2, '1011010110' ),
    ( 20, 1, '11111011101010111111' ),
    ( 30, 7, '011100001010011011100001010011' ),
    ( 39, 6, '110100111111101000011000100110111100010' ),
    ( 53, 9,
      '''01011001011111001000111001111010010010100010000010110''' ),
    ( 120, 7,
      '''10101101100001000001010110010111110101111010011101001100000010001010011010110000
      0000100110010100010010110111000000010110''' ),
    ( 220, 27,
      '''11101111111010001001100110011001101000000010100011000111101100111111000001010000
      10101101100111001000100110110101111000110101101000010000100110111101001001011010
      110100100111011000110001101011110100110011010111110101010100''' ),
    ( 500, 87,
      '''10100011011010011100011010010001010101000001111111001101011000000011001111111011
      10011100110101111110110101000100110110011001101110011011100001000111110101011111
      11001111000011001100111011101011000011111100010010011010001111000000101110101101
      10101000011000111110001110010001011010001011111111101111000000011111010001000000
      11100111101111010100100110000001000101000011101011010011010110011110111000010010
      01111001000110100101100010000111001010011110111010001001011001111011111011010110
      10101101111011101110''' ),
    ( 1002, 83,
      '''00101001001001010000001101011111111010111101000101111110001110000110110110010101
      11101100110111011001101110011101100100111101111010110011110101100001101010100011
      11100011000111111101000111101001111111000011001011100110101100001101000001110010
      01101000001001001000000110100000101111001110001110011110101001100111101101010000
      01010100000110100111101010010010010000000011000100011011011001111010001101111000
      01000010110100110010101110011111001100010011111110101101001100111101110000000000
      11011001000000110000100101000101010010001100001000101001100110010100001000001101
      11010001000010100110001010011010001000100011010001011101010100011101001101101100
      01111101001100110011110000000010010010011001111001011111000010110000110010101000
      10110011001111010001010001100001110101000010011011010111001101011001111000001011
      11101010101011011110111111101000011001101000101100110011010000110000011011110011
      00100000100000001111011010000011111011110100111110010101100011101001111101010000
      111110001001100111011111100010100000010101''' ),
    ( 2107, 108,
      """01111101000110000111111011100101011000111001111011101001001110111110001100011001
      10010101001010111011010010000101111111111001101010111011110100100101000101100011
      11101000100100101011101000001111001010000111101011111100010010110000100110100100
      01001101011100101100111100101011011001111110010011000110110111010110010100101110
      01111111011100001110011111001000100100011010110011000101100111111001011110101110
      01110101101111101101010001011001000110001011000011011110001111100110100010100101
      11011111001100110011100100100010101011111000001001000110011110010011011101110100
      10111111001100100110000101100101101010100110101000011011110001010000010001000110
      10011101010010011101101111110100110101111111011001000110111001000011101101110001
      00000111111010000101010111110110110000111111000000011100010011011001011000110101
      11010111111000011000101100101100110000000001001111100101110100100011011010011100
      00000011110101010001110110001101101000011010110011100110111010111110110000010000
      10001010011110010001100001010100000101111011100001000110001100010000001011101110
      10011111101000100100000110001001010101011001001001110110101000001001001100001011
      00110111000111111001110011101011011100010111010000010011110110011011000011101001
      11110110100100001011110000100000011001101001011101001000010101001001011111111011
      10001110001000011011001011101000111111001011001111101111110110101111101111011111
      10011111001101011101011111100100101011011111111111000100100111100011101110110100
      01000110110010101101001011010000001100100010010001001110110100011111100011111101
      01001101111011010101010101001101100110110001111111000100000111011010101011000010
      00110111101101101101000110011011110010001000000011110011100111100000001010010011
      10000111011111000001010101010100101001011010001011010100011011001110110010100000
      10001111011110000101111111010101101101110110001111100011001110000100100101001111
      00001111111000100110010100000101101110001000110110001000001100110000001011000010
      10001011011100001011001000101011111000111000010010111101000010000110011010000001
      00100011000010000011001101111101001001111001100110001000100101011111001011001111
      110001011111001101010101001""" )
)

def getA( N, M, delay=0 ):
    R = range(N)
    lists_for_M = [ [ (j+k+delay) % N for k in range(M) ]
                    for j in R ]
    return matrix( F, N, N, [ [ F(1) if k in lists_for_M[j]    else F(0)
                                for k in R ]
                              for j in R ] ).transpose()

def showVector( vec, separator='' ):
    return separator.join( [ str( entry ) for entry in vec ] )

def exchange( wblocks, wpattern, b, k1, k2 ):
    blocks, pattern = wblocks[:], wpattern[:]    # copy the information

    for block in blocks:
        block[k1] = F(1) - block[k1]
        block[k2] = F(1) - block[k2]

    pattern[k1] = b - pattern[k1]
    pattern[k2] = b - pattern[k2]

    return blocks, pattern

def blocksInformation( blocks ):
    print "Blocks:"
    for block in blocks:
        print showVector( block )
    print

# main search for all cases...
def searchLampSwitches( N, m, lamps
                        , showBlocks=False
                        , returnSolution=False ):
    """N, m, lamps is an entry in CASES..."""
    print N, m, lamps

    M = 2*m+1
    d = gcd( N, M )
    R = range( d )           # we will often loop using R
    b = ZZ( N/d )            # number of blocks
    bound = (b/2).floor()    # critical bound for the entries in pattern

    print "N=%s M=%s d=gcd(N,M)=%s b=N/d=%s bound=%s" % ( N, M, d, b, bound )

    A = getA( N, M, delay=-m )
    v = matrix( F, N, 1, [ F(int(s)) for s in lamps if s in '01' ] )
    w = vector( A.solve_right( v ) )

    if d == 1:
        # then w is already the (unique, thus optimal) solution
        print "UNIQUE SOLUTION"
        print sum( [ 1 for entry in w if entry ] )
        print showVector( w )

        return w if returnSolution else None

    # else we build blocks
    wblocks = [ [ w[ j + d*k ] for j in R ]
               for k in range(N/d) ]

    wpattern = [ sum( [ 1 for wblock in wblocks if wblock[k] ] )
                 for k in R ]
    print "Initial pattern:",
    print showVector( wpattern, separator = '' if b<10 else ',' )

    if showBlocks:
        blocksInformation( wblocks )

    wplaces = [ k for k in R if wpattern[k] > bound ]    # suboptimal places in wpattern
    wplaces . sort( lambda k1, k2:    cmp( -wpattern[k1], -wpattern[k2] ) )
    print "Suboptimal places:", wplaces

    while len( wplaces ) > 1:
        k1, k2  = wplaces[:2]
        wplaces = wplaces[2:]
        wblocks, wpattern = exchange( wblocks, wpattern, b, k1, k2 )
        print "New pattern:",
        print showVector( wpattern, separator = '' if b<10 else ',' )
        if showBlocks:
            blocksInformation( wblocks )

    # we count solutions, last changes can be done - but the   in case...
    if wplaces:
        k, = wplaces
        # one last move is possible, if there are places with entries > then opposite of k'th place
        # examples:
        # b = 8 or 9, bound = 4, and
        # ---> wpattern is 00011122233349 - then exchange 49
        # ---> wpattern is 00011122233339 - then exchange 39
        # ---> wpattern is 00011122222225 - no good exchange, 5 becomes 3 or 4, but the 2 (best choice) becomes > 5 

        goodoppositeplaces = [ kk for kk in R if kk != k and wpattern[kk] > b - wpattern[k] ]
        if goodoppositeplaces:
            goodoppositeplaces.sort( lambda k1, k2:    -cmp( wpattern[k1], wpattern[k2] ) )
            # we can still get an optimization...
            kk = goodoppositeplaces[0]
            print "Last exchange possible, place %s can be moved (using place %s)" % ( k, kk )
            wblocks, wpattern = exchange( wblocks, wpattern, b, k, kk )
            wplaces = [ kk, ] if kk > bound else []
            print "New pattern:",
            print showVector( wpattern, separator = '' if b<10 else ',' )
            if showBlocks:
                blocksInformation( wblocks )

    if wplaces:
        k, = wplaces
        oppositeplaces = [ kk for kk in R if wpattern[kk] + wpattern[k] == b ]
        if not oppositeplaces:
            print "UNIQUE SOLUTION, place %s cannot be moved" % k
        else:
            L = len( oppositeplaces )
            print ( "%s = 2^%s SOLUTIONS, obtained by interchanging even number of positions in %s"
                    % ( 2**L, L, str( [k, ] + oppositeplaces ) ) )
    else:
        if b == 2*bound+1:
            print "UNIQUE SOLUTION, all suboptimal places could be paired"
        else:
            midplaces = [ kk for kk in R if wpattern[kk] == bound ]
            L = len( midplaces )
            if L == 0 :
                print "UNIQUE SOLUTION, all suboptimal places could be paired, none equal %s remained" % bound
            elif L == 1:
                print "UNIQUE SOLUTION, one middle place remained"
            else:
                print ( "%s = 2^%s SOLUTIONS, obtained by interchanging even number of middle positions in %s"
                        % ( 2**(L-1), L-1, str(midplaces) ) )

    print "OPTIMAL NUMBER OF SWITCHES: %s" % sum(wpattern)
    if not returnSolution:
        return

    sol = []
    for wblock in wblocks:
        sol += wblock
    return sol


for N, m, lamps in CASES:
    searchLampSwitches( N, m, lamps )
    print 60*'.'

This delivers the solutions. I hope there are no problems with the above search logic (in some other particular cases).

case (0) For this, let us take the cases one by one...

sage: searchLampSwitches( *CASES[0], showBlocks=1, returnSolution=1 )
6 1 101101
N=6 M=3 d=gcd(N,M)=3 b=N/d=2 bound=1
Initial pattern: 101
Blocks:
101
000

Suboptimal places: []
2 = 2^1 SOLUTIONS, obtained by interchanging even number of middle positions in [0, 2]
OPTIMAL NUMBER OF SWITCHES: 2
[1, 0, 1, 0, 0, 0]

Here, the code solves the linear system, the first solution is 101 000 - splitted in two blocks - and writing the blocks over each other it is easy to see the pattern 101. All entries in the pattern are $\le$ bound, so this is already a solution.

Is there any other solution? Yes, the two places with the reached bound can be inverted in the same time, so we pass from

101
000
* *

to 000 101

The printed solution is simply the concatenation of the blocks (of the first solution found).

case (1)

sage: searchLampSwitches( *CASES[1], showBlocks=1 )
10 2 1011010110
N=10 M=5 d=gcd(N,M)=5 b=N/d=2 bound=1
Initial pattern: 21111
Blocks:
11111
10000

Suboptimal places: [0]
Last exchange possible, place 0 can be moved (using place 1)
New pattern: 01111
Blocks:
00111
01000

8 = 2^3 SOLUTIONS, obtained by interchanging even number of middle positions in [1, 2, 3, 4]
OPTIMAL NUMBER OF SWITCHES: 4

So the first solution given by a sage solve had the pattern 21111 and the sum of the entries is 6. We can do better, e.g. inverting the places 0 and 1. (Or 0 and 2, or 0 and 3, or...) Doing this the pattern moves from

21111
*        to
01111

which is better, the number of switches is 4, the sum of the entries in this pattern.

case (2)

sage: searchLampSwitches( *CASES[2], showBlocks=1 )
20 1 11111011101010111111
N=20 M=3 d=gcd(N,M)=1 b=N/d=20 bound=10
UNIQUE SOLUTION
8
01001010011100010010

case (3)

sage: searchLampSwitches( *CASES[3], showBlocks=1 )
30 7 011100001010011011100001010011
N=30 M=15 d=gcd(N,M)=15 b=N/d=2 bound=1
Initial pattern: 111101011001000
Blocks:
111101011001000
000000000000000

Suboptimal places: []
128 = 2^7 SOLUTIONS, obtained by interchanging even number of middle positions in [0, 1, 2, 3, 5, 7, 8, 11]
OPTIMAL NUMBER OF SWITCHES: 8

case (4)

sage: searchLampSwitches( *CASES[4] )
39 6 110100111111101000011000100110111100010
N=39 M=13 d=gcd(N,M)=13 b=N/d=3 bound=1
Initial pattern: 3200221112201
Suboptimal places: [0, 1, 4, 5, 9, 10]
New pattern: 0100221112201
New pattern: 0100111112201
New pattern: 0100111111101
UNIQUE SOLUTION, all suboptimal places could be paired
OPTIMAL NUMBER OF SWITCHES: 9

The initial pattern was changed as follows:

**  **   **
3200221112201
||
0100221112201
    ||
0100111112201
         ||
0100111111101

and each change was moving an entry to the opposite one, entry -> 3-entry where 3 is the value of b. To see the blocks from one step to the next one, use searchLampSwitches( *CASES[4], showBlocks=True ) .

case (5)

sage: searchLampSwitches( *CASES[5] )
53 9 01011001011111001000111001111010010010100010000010110
N=53 M=19 d=gcd(N,M)=1 b=N/d=53 bound=26
UNIQUE SOLUTION
25
00100010111110010100010100111011100010110001000011101

case (6)

sage: searchLampSwitches( *CASES[6] )
120 7 10101101100001000001010110010111110101111010011101001100000010001010011010110000
      0000100110010100010010110111000000010110
N=120 M=15 d=gcd(N,M)=15 b=N/d=8 bound=4
Initial pattern: 543553565644234
Suboptimal places: [7, 9, 0, 3, 4, 6, 8]
New pattern: 543553525244234
New pattern: 343353525244234
New pattern: 343333325244234
Last exchange possible, place 8 can be moved (using place 1)
New pattern: 343333323244234
8 = 2^3 SOLUTIONS, obtained by interchanging even number of middle positions in [1, 10, 11, 14]
OPTIMAL NUMBER OF SWITCHES: 46

case (7)

sage: searchLampSwitches( *CASES[7] )
220 27 11101111111010001001100110011001101000000010100011000111101100111111000001010000
      10101101100111001000100110110101111000110101101000010000100110111101001001011010
      110100100111011000110001101011110100110011010111110101010100
N=220 M=55 d=gcd(N,M)=55 b=N/d=4 bound=2
Initial pattern: 2202111113323112222323223212121310210122201222122130112
Suboptimal places: [9, 10, 12, 19, 21, 24, 31, 50]
New pattern: 2202111111123112222323223212121310210122201222122130112
New pattern: 2202111111121112222123223212121310210122201222122130112
New pattern: 2202111111121112222121221212121310210122201222122130112
New pattern: 2202111111121112222121221212121110210122201222122110112
8388608 = 2^23 SOLUTIONS, obtained by interchanging even number of middle positions in [0, 1, 3, 11, 15, 16, 17, 18, 20, 22, 23, 25, 27, 29, 34, 38, 39, 40, 43, 44, 45, 47, 48, 54]
OPTIMAL NUMBER OF SWITCHES: 74

case (8)

sage: searchLampSwitches( *CASES[8] )
500 87 10100011011010011100011010010001010101000001111111001101011000000011001111111011
      10011100110101111110110101000100110110011001101110011011100001000111110101011111
      11001111000011001100111011101011000011111100010010011010001111000000101110101101
      10101000011000111110001110010001011010001011111111101111000000011111010001000000
      11100111101111010100100110000001000101000011101011010011010110011110111000010010
      01111001000110100101100010000111001010011110111010001001011001111011111011010110
      10101101111011101110
N=500 M=175 d=gcd(N,M)=25 b=N/d=20 bound=10
Initial pattern: 12,7,11,11,6,7,2,7,10,7,10,11,8,11,9,11,12,9,10,8,11,9,8,8,9
Suboptimal places: [0, 16, 2, 3, 11, 13, 15, 20]
New pattern: 8,7,11,11,6,7,2,7,10,7,10,11,8,11,9,11,8,9,10,8,11,9,8,8,9
New pattern: 8,7,9,9,6,7,2,7,10,7,10,11,8,11,9,11,8,9,10,8,11,9,8,8,9
New pattern: 8,7,9,9,6,7,2,7,10,7,10,9,8,9,9,11,8,9,10,8,11,9,8,8,9
New pattern: 8,7,9,9,6,7,2,7,10,7,10,9,8,9,9,9,8,9,10,8,9,9,8,8,9
4 = 2^2 SOLUTIONS, obtained by interchanging even number of middle positions in [8, 10, 18]
OPTIMAL NUMBER OF SWITCHES: 204

case (9)

The output needs a different width, but searchLampSwitches( *CASES[9] ) returns with no problems a long mess ending with:

New pattern: 23323322012222322331131122211213222333221213322223312122223212221213222322132131212212332123223232223021321133122121221223122322233222122132231331101333212232123243212
Last exchange possible, place 162 can be moved (using place 1)
New pattern: 23323322012222322331131122211213222333221213322223312122223212221213222322132131212212332123223232223021321133122121221223122322233222122132231331101333212232123223212
8796093022208 = 2^43 SOLUTIONS, obtained by interchanging even number of middle positions in [1, 2, 4, 5, 14, 17, 18, 21, 31, 35, 36, 37, 43, 44, 49, 50, 58, 67, 71, 75, 78, 86, 87, 91, 94, 96, 100, 104, 108, 109, 121, 125, 129, 130, 138, 141, 143, 144, 149, 150, 151, 156, 160, 163]
OPTIMAL NUMBER OF SWITCHES: 334

case (10)

The call of searchLampSwitches( *CASES[10] ) returns after computing the solution...

N=2107 M=217 d=gcd(N,M)=7 b=N/d=301 bound=150
Initial pattern: 142,160,145,155,153,142,138
Suboptimal places: [1, 3, 4]
New pattern: 142,141,145,146,153,142,138
UNIQUE SOLUTION, place 4 cannot be moved
OPTIMAL NUMBER OF SWITCHES: 1007

That is all so far.