2
$\begingroup$

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.

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ 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 :-) $\endgroup$
    – leoll2
    May 4, 2015 at 13:59
  • 4
    $\begingroup$ @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. $\endgroup$
    – Set Big O
    May 4, 2015 at 16:09
  • $\begingroup$ @leoll2 Yes, or if one could solve it without computer, it suits me fine. Well, it is now in codegolf.stackexchange.com/questions/49620/… $\endgroup$
    – selfstudying
    May 4, 2015 at 16:58
  • $\begingroup$ possible duplicate of Turn off all lights in a ring-shaped palace $\endgroup$
    – A.D.
    May 4, 2015 at 18:55

1 Answer 1

Reset to default
1
$\begingroup$

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$.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Well, it looks like we're going way off Puzzling with this question... $\endgroup$
    – leoll2
    May 4, 2015 at 19:48

Not the answer you're looking for? Browse other questions tagged or ask your own question.