# Shutting down all lamps [closed]

I found this problem from http://artofproblemsolving.com/community/c163h564755p3301930 .

I have $n=2017$ lamps in a circle, and enumerated by $L_1,\ldots,L_n$. Some of them are switched on and some of them are switched off. I also have been given a positive integer $m=108$. One every turn I choose one lamp $L_i$ and then the lamps $L_{i-m},\ldots,L_{l+m}$ will change their state, I mean if lamp $L_j$ was turned off then now it is turned on and vice versa. Also indexes go around like $L_0=L_n, L_{-1}=L_{n-1}$. What is the minimum number of turns to shut off all lamps, and what are the switches I need to press to shut down the lamps?

The lamp states from the beginning are

                                    0111110100011000011111101110010101100011
1001111011101001001110111110001100011001
1001010100101011101101001000010111111111
1001101010111011110100100101000101100011
1110100010010010101110100000111100101000
0111101011111100010010110000100110100100
0100110101110010110011110010101101100111
1110010011000110110111010110010100101110
0111111101110000111001111100100010010001
1010110011000101100111111001011110101110
0111010110111110110101000101100100011000
1011000011011110001111100110100010100101
1101111100110011001110010010001010101111
1000001001000110011110010011011101110100
1011111100110010011000010110010110101010
0110101000011011110001010000010001000110
1001110101001001110110111111010011010111
1111011001000110111001000011101101110001
0000011111101000010101011111011011000011
1111000000011100010011011001011000110101
1101011111100001100010110010110011000000
0001001111100101110100100011011010011100
0000001111010101000111011000110110100001
1010110011100110111010111110110000010000
1000101001111001000110000101010000010111
1011100001000110001100010000001011101110
1001111110100010010000011000100101010101
1001001001110110101000001001001100001011
0011011100011111100111001110101101110001
0111010000010011110110011011000011101001
1111011010010000101111000010000001100110
1001011101001000010101001001011111111011
1000111000100001101100101110100011111100
1011001111101111110110101111101111011111
1001111100110101110101111110010010101101
1111111111000100100111100011101110110100
0100011011001010110100101101000000110010
0010010001001110110100011111100011111101
0100110111101101010101010100110110011011
0001111111000100000111011010101011000010
0011011110110110110100011001101111001000
1000000011110011100111100000001010010011
1000011101111100000101010101010010100101
1010001011010100011011001110110010100000
1000111101111000010111111101010110110111
0110001111100011001110000100100101001111
0000111111100010011001010000010110111000
1000110110001000001100110000001011000010
1000101101110000101100100010101111100011
1000010010111101000010000110011010000001
0010001100001000001100110111110100100111
1001100110001000100101011111001011001111
110001011111001101010101001


It looks like Gaussian elimination on $\mathbb Z/2\mathbb Z$ but I have no program to do it.

• Welcome to Puzzling SE! Are you asking for a program to solve this problem? If so, codegolf.stackexchange.com would be a more appropriate place to do it :-) May 4 '15 at 13:59
• @leoll2 As it stands, this would be closed at PPCG. Simply asking for code isn't welcome there. It could be modified to make it a proper challenge, but it would take some looking around to see how things are done. May 4 '15 at 16:09
• @leoll2 Yes, or if one could solve it without computer, it suits me fine. Well, it is now in codegolf.stackexchange.com/questions/49620/… May 4 '15 at 16:58
• possible duplicate of Turn off all lights in a ring-shaped palace
– A.D.
May 4 '15 at 18:55

Let $A$ be a $2017\times 2017$ matrix in $\mathbb Z_2$, where $A_{ij}=1$ precisely when pressing lamp $i$ will also change lamp $j$ (namely, when $j-i\in \{-m,-(m-1),\dots,m-1,m\}$). Let $b$ be a $2017$ entry column vector in $\mathbb Z_2$, which is the initial state of the lamps. You want to solve the equation $$Ax=b$$ where $x$ is a vector representing whether or not you should toggle lamp $i$. The solution is $x=A^{-1}b$, so to solve this, you could compute $A^{-1}$ by Gaussian elimination. If you remember how this algorithm works, and are familiar with coding, then you should be able to translate it into code, as long as you are careful to make sure you perform your addition over $\mathbb Z_2$ as opposed to $\mathbb R$.