Combinatorics – Lights Out Variant: Flipping the Whole Row and Column

algorithmscombinatoricspuzzle

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?

Best Answer

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.

Related Question