Revision history - ASKSAGE: Sage Q&A Forum

[disclaimer : i started to write my answer before the numbers changed]

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=MI $, 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 $, which is equivalent to$ MI = L_init $(remember that in$ F $,$ 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: M.right_kernel() 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 M.right_kernel(M)]) 1007

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

[disclaimer : i started to write my answer before the numbers changed]

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=MI$,~~ $L=M*I$ , where $M$ is the matrix over $F$ where $M_{i,j}=1$ iff $j $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 $, which is equivalent to$ MI = L_init$ (remember that in ~~$F$ ,~~ $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' '0111110100011000011111101110010101100011100111101110100100111011111000110001100110010101001010111011010010000101111111111001101010111011110100100101000101100011111010001001001010111010000011110010100001111010111111000100101100001001101001000100110101110010110011110010101101100111111001001100011011011101011001010010111001111111011100001110011111001000100100011010110011000101100111111001011110101110011101011011111011010100010110010001100010110000110111100011111001101000101001011101111100110011001110010010001010101111100000100100011001111001001101110111010010111111001100100110000101100101101010100110101000011011110001010000010001000110100111010100100111011011111101001101011111110110010001101110010000111011011100010000011111101000010101011111011011000011111100000001110001001101100101100011010111010111111000011000101100101100110000000001001111100101110100100011011010011100000000111101010100011101100011011010000110101100111001101110101111101100000100001000101001111001000110000101010000010111101110000100011000110001000000101110111010011111101000100100000110001001010101011001001001110110101000001001001100001011001101110001111110011100111010110111000101110100000100111101100110110000111010011111011010010000101111000010000001100110100101110100100001010100100101111111101110001110001000011011001011101000111111001011001111101111110110101111101111011111100111110011010111010111111001001010110111111111110001001001111000111011101101000100011011001010110100101101000000110010001001000100111011010001111110001111110101001101111011010101010101001101100110110001111111000100000111011010101011000010001101111011011011010001100110111100100010000000111100111001111000000010100100111000011101111100000101010101010010100101101000101101010001101100111011001010000010001111011110000101111111010101101101110110001111100011001110000100100101001111000011111110001001100101000001011011100010001101100010000011001100000010110000101000101101110000101100100010101111100011100001001011110100001000011001101000000100100011000010000011001101111101001001111001100110001000100101011111001011001111110001011111001101010101001' sage: d = 2107 sage: m = 108 sage: F = GF(2) GF(2) sage: L_init = vector(F,input) 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 1 sage: M 2107 x 2107 dense matrix over Finite Field of size 2 (use the '.str()' method to see the entries)entries)

We get a solution of the problem by solving the equation $M*I = L_init$ :

sage: I = M.solve_right(L_init)M.solve_right(L_init)

We can see that this particular solution has 1035 solutions

sage: len(I.nonzero_positions()) 10351035

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: M.right_kernel() 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 22

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 M.right_kernel(M)]) 10071007

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

[disclaimer : i started to write my answer before the numbers changed]

First, it should be clear that testing all the ~~$2^2107$~~ $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 $, which 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: M.right_kernel()
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$ .~~ $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 M.right_kernel(M)])
1007

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

[disclaimer : i started to write my answer before the numbers changed]

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 $, which 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: M.right_kernel()
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 M.right_kernel(M)])
K])
1007

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

[disclaimer : i started to write my answer before the numbers changed]

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$ )~~ $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+M~~$L_{init}+MI = 0 $, which is equivalent to$ MI = ~~L_init$~~ 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$:~~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 $M~~S=L_init$~~ S=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.

[disclaimer : i started to write my answer before the numbers changed]

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 $, which 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: 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(v)
sage: K = M.right_kernel() ; K
Vector space of degree 120 and dimension 14 over Finite Field of size 2
Basis matrix:
14 x 120 dense matrix over Finite Field of size 2
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.

~~[disclaimer :~~ [Note that i started to write my answer before the numbers ~~changed]~~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 $, which 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: 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(v)
sage: K = M.right_kernel() ; K
Vector space of degree 120 and dimension 14 over Finite Field of size 2
Basis matrix:
14 x 120 dense matrix over Finite Field of size 2
sage: min([len((I+k).nonzero_positions()) for k in K])
46

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.

[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 $, which 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: 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(v)
sage: K = M.right_kernel() ; K
Vector space of degree 120 and dimension 14 over Finite Field of size 2
Basis matrix:
14 x 120 dense matrix over Finite Field of size 2
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$~~ $2^{14}=16384$ solutions.

[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}+M~~$ L_{init}+MI = ~~0$,~~ 0 $, which is equivalent to $M$ MI = ~~L_{init}$~~ 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: 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(v)
sage: K = M.right_kernel() ; K
Vector space of degree 120 and dimension 14 over Finite Field of size 2
Basis matrix:
14 x 120 dense matrix over Finite Field of size 2
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.

[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 $, which 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 $M$ M~~S=L_{init}$~~ S=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: 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(v)
sage: K = M.right_kernel() ; K
Vector space of degree 120 and dimension 14 over Finite Field of size 2
Basis matrix:
14 x 120 dense matrix over Finite Field of size 2
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.

[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 ~~$, which~~ $ 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: 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(v)
sage: K = M.right_kernel() ; K
Vector space of degree 120 and dimension 14 over Finite Field of size 2
Basis matrix:
14 x 120 dense matrix over Finite Field of size 2
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.

[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(v)
M.solve_right(L_init)
sage: K = M.right_kernel() ; K
Vector space of degree 120 and dimension 14 over Finite Field of size 2
Basis matrix:
14 x 120 dense matrix over Finite Field of size 2
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.

Revision history [back]