Revision history [back]
 | 1 | initial version |
[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.
| | 2 | No.2 Revision |
[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):
We get a solution of the problem by solving the equation $M*I = L_init$:
We can see that this particular solution has 1035 solutions
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:
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:
So, the minimum number of turns to shut off all lamps is 1007.
| | 3 | No.3 Revision |
[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.
| | 4 | No.4 Revision |
[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.
| | 5 | No.5 Revision |
[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 $MS=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.
| | 6 | No.6 Revision |
[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.
| | 7 | No.7 Revision |
[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.
| | 8 | No.8 Revision |
[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.
| | 9 | No.9 Revision |
[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.
| | 10 | No.10 Revision |
[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$ MS=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.
| | 11 | No.11 Revision |
[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.
| | 12 | No.12 Revision |
[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.
