Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

So I found this puzzle similar to Lights Out, if any of you have ever played that. Basically the puzzle works in a grid of lights like so:

1 0 0 0
0 0 0 0
0 1 0 0
0 0 1 0

When you selected a light (the X), it toggled itself and all the lights in its row and column:

1 0 1 0
1 1 X 1
0 1 1 0
0 0 0 0

This got me wondering how one could tell whether there was a solution for a given setup and grid size, and if so, what was it? I can't seem to get anywhere. Could anyone push me in the right direction?

share|improve this question
    
For starters, if the grid is $m\times n$ where exactly one of $m$ and $n$ are even, then a move can never change the parity of the number of lights that are on. Other than that, I'm intrigued myself. –  Arthur Jul 11 '13 at 20:37
    
Where did you find this problem? –  Aryabhata Jul 12 '13 at 0:30
    
I found this in a game on the iPod touch, actually. It is called Doors & Rooms. It's a puzzle game. –  Numeri Jul 12 '13 at 2:46

2 Answers 2

up vote 6 down vote accepted

Think of each light as a variable taking values in $0, 1$. Flipping a switch has the effect of adding $1$ to each corresponding light, modulo $2$. To the switch at position $i, j$ make correspond a variable $s_{i,j}$representing the number of times you flip that switch. Now the final value of each light is equal to its initial value plus each $s_{i,j}$ that shares a column or row with it - this is a linear equation in the variables $s_{i,j}$. For an $m\times n$ grid, we thus obtain $mn$ linear equations (one for each light) in $mn$ variables (one for each switch).

The integers modulo $2$ are a field, so all of the usual results of linear algebra should apply.

Example. Let's works out the $2\times2$ case. Which grids are solvable?

If we represent "on" as $1$ and "off" as $0$, then note that we need to add each light to itself. That is, if a light starts at value $0$, we need to flip the switches so as to add $0$ to that light (because we don't want it to change), but if it starts at value $1$, we need to flip the switches so as to add $1$ to that light. So the equation for each light is going to look like sum of associated switches = initial state.

Writing the initial state of the $i,j$ light as $l_{i,j}$, we therefore need to solve:

$$l_{1,1}=s_{1,1}+s_{1,2}+s_{2,1}$$ $$l_{1,2}=s_{1,2}+s_{1,1}+s_{2,2}$$ $$l_{2,1}=s_{2,1}+s_{1,1}+s_{2,2}$$ $$l_{2,2}=s_{2,2}+s_{1,2}+s_{2,1}$$

The matrix for this system looks like this (omitting zeros for readability):

\begin{array}{cccc} 1 & 1 & 1 & \\ 1 & 1 & & 1 \\ 1 & & 1 & 1 \\ & 1 & 1 & 1 \end{array}

Gaussian Elimination works easily on this matrix (tip: remember that mod $2$, $a + a = 0$ for any $a$) and we obtain an explicit solution for the general $2\times2$ grid:

$$s_{1,1}=l_{1,1}+l_{1,2}+l_{2,1}$$ $$s_{1,2}=l_{1,2}+l_{1,1}+l_{2,2}$$ $$s_{2,1}=l_{2,1}+l_{1,1}+l_{2,2}$$ $$s_{2,2}=l_{2,2}+l_{1,2}+l_{2,1}$$

So the answer is that all $2\times2$ grids are solvable, and there's the solution (concurring with Aryabhata's proposition).

As the number of equations is equal to the number of cells on the grid, this method quickly becomes too tedious and complicated to perform by hand. I would try to investigate the determinant of these matrices in the abstract case and see if you come up with anything. That would at least tell you which grid sizes have a guaranteed solution.

share|improve this answer
    
Thank you so much! –  Numeri Jul 12 '13 at 17:41
    
@Numeri No problem. Epilogue: Although the calculations are indeed too heavy to perform by hand, I did get the above method set up in Sage, and tested it out against a Flash game with complete success. –  Jack M Jul 12 '13 at 20:43

First, consider the $n\times n$ case.

I claim the following:

Claim:

If $n$ is even, there is always a solution given any starting configuration.

If $n$ is odd, there is a solution iff the 'on' lights parities for each row and column are the same.

i.e. if the lights were $1$ for on and $0$ for off, then modulo $2$, the sum of each individual row, and sum of each individual column must be the same.

Proof:

Case I: $n$ is even. You can toggle just a particular light by toggling all the lights in its row and column. So you can switch off all the lights by going after individual lights.

Case II: $n$ is odd.

Notice that if $n$ is odd, on any single operation, all the row and column parities change simultaneously.

Thus if they are not all the same, we can never achieve all lights off. This shows the necessity of the parities being the same.

To prove sufficiency, consider an arrangement of $(2k+1)\times(2k+1)$ which has all row and column parities the same.

Consider the $2k\times 2k$ subgrid which does not include the bottom row and the right column. Use the above even $n$ case algorithm to switch off all the lights in that $2k\times 2k$ grid. Since the row and column parities all flip together and were initially all the same, we must have that the remaining lights, in the bottom row and right column, are all the same (including the bottom right corner). Now we toggle the bottom right corner, if needed.

$\circ$

Now, the above can be generalized to the $m \times n$ case, when $m$ and $n$ have the same parity.

If $m$ and $n$ have different parities, there is more work to be done.

share|improve this answer
    
Thanks for your help! I was looking for hints, not answers, otherwise I would have marked this as the answer. :D –  Numeri Jul 12 '13 at 17:42

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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