Turn on all squares

Question

Take a square grid of size $a\times b$, with all squares being off. You can tap a square, to reverse the state of that square and all squares located in the same column and row as the tapped square. Your goal is to turn on all the squares.

What's the minimal amount of moves required to solve a given grid?

Can there be a general strategy to optimally solve any given grid?

---

Let $a,b\gt1$, since the grid is solved in one move otherwise.

Solution in $a\times b$ moves

If $a+b$ is even, then we can solve the grid by tapping each square exactly once, in any order; this works since each square gets triggered odd amount of times which means it will be turned on.

Solution in $a$ or $b$ moves

If $a$ is odd, we can solve a grid by tapping each square in a single row.
If $b$ is odd, we can solve a grid by tapping each square in a single column.

$5\times5$ solution example:

---

I believe the second solution is optimal when one of $a,b$ is odd, and that the first solution is optimal when both are even.

But I'm not sure if the first solution is optimal?
Can we solve a $2n\times2m$ grid in less than $4nm$ moves? (why not?)

---

---

Secondly; we can reach a checkerboard state in grids where $a,b$ are even by tapping each square in every second diagonal (either left or right diagonals only).

$4\times4$ example:

Can we reach a checkerboard state in any other grids? (why not?)

Answer 1

Here is a more straightforward proof than the one given by ffao, plus information about checkerboard patterns

This game is a version of Lights Out. Like all these games, they have the following properties:

1. The order of moves does not matter. If you look at the effect of a move sequence on a single square, all that matters to that square is how often it is toggled. It does not matter to that square what order the moves are performed, as all the moves that affect it will affect it in the same way.

2. Each square need not be tapped more than once. If you were to tap a square more than once during a solution, you can reorder the moves to make those two taps consecutive. But tapping a square twice has no net effect, so such repeated moves can be skipped.

This means that there are only $2^{a*b}$ possible move sequences that need to be considered - each square can either be tapped or not by the move sequence.

Boards with only even dimensions

Consider now an ideal situation in which it is possible by some sequence of taps to change the state of just a single square without affecting the rest.

By rearranging the rows and columns of that sequence of taps, any single square can be changed. Therefore every state combination can be achieved from the all-off state.

In this ideal situation, all $2^{a*b}$ state patterns can be achieved. Since there are only $2^{a*b}$ move sequences, every combination of states has a unique solution.

For $a\times b$ boards with both $a$ and $b$ even, we are in this ideal situation, because tapping a square together with all the squares in the same row or column changes only that single square (it toggles $a+b-1$ times, the column $a$ times, the row $b$ times, the rest $2$ times).

We know that tapping every square will change the all-off state to all-on (everything toggles $a+b-1$ times) and from the above we know that this is the unique solution so $a*b$ moves are necessary.

This also means that a checkerboard pattern is always possible, and that when you have found a solution, the solution will be unique. It is easy to see that tapping out a checkerboard pattern will create a checkerboard state pattern (untapped squares toggle $(a+b)/2$ times, tapped square $(a+b)/2-1$ times), so a total of $a*b/2$ taps are always needed.

Boards with odd dimensions

If $a$ is odd, then we are not in this ideal situation. This is easy to see because pressing the squares a single row toggles everything. So we can get from all-off to all-on by pressing either the first row, or the second row, etc. This pattern clearly does not have a unique solution.

This can allow for shorter solutions to those patterns that can be achieved. Because tapping all the squares of any two rows will have no effect on the state, any move sequence that uses more than $a$ taps on a pair of rows can be shortened - just exchange the tapped squares for the untapped ones on those rows.

Unfortunately it is not possible to create a checkerboard pattern starting from the all-off state. If you look at two rows of the board, every possible move changes the state of an even number of squares in those two rows. If you start from an all-off state, there will always be an even number of squares off and an even number on on those two rows. For a checkerboard pattern we want exactly $a$ of the squares on, which is therefore not possible.

Of course the same results hold if $b$ is odd, or if both $a$ and $b$ are odd.

Answer 2

Making a board with even side lengths completely black

(Note: I'll abuse notation here and have $a+b$ mean the parity of the sum a+b. This should help me avoid typing mod 2 everywhere.)

First note that the order of the presses does not matter, and that pressing a button twice is the same as not pressing it at all, so we should only consider which buttons are pressed and which aren't. Alternatively, let's say that we should paint the pressed buttons black, and leave the others white.

Furthermore, at least one button must be pressed, otherwise the board will be all white. Without loss of generality, assume (1,1) is black.

Let $x_{ij}$ be 1 if the button on (i,j) is black, 0 otherwise. $r_i = \sum_{j=1}^b x_{ij}$ is the parity of buttons in a row and $c_j = \sum_{i=1}^a x_{ij}$ is the parity of buttons in column j.

The final color of square $(i,j)$ is then $C(i,j) = r_i + c_j - x_{ij}$. Let's prove the following condition for all final squares being the same.

Lemma: All squares end with the same color if and only if the following conditions hold:

• Two squares in the same row are colored the same if and only if their column parity is the same.
• Two squares in the same column are colored the same if and only if their row parity is the same.

Proof: $C(i, j) = C(k, j) \iff r_i + c_j - x_{ij} = r_k + c_j - x_{kj} \iff x_{ij} = x_{kj} $. The same argument works for two squares in the same row.

From the lemma, we have by relating the squares $(1,1)$, $(1,j)$, $(i,1)$ and $(i,j)$:

$$x_{ij} + r_i = x_{1j} + r_1 \\ x_{1j} + c_j = x_{11} + c_1 \\ x_{ij} + c_j = x_{i1} + c_1 \\ x_{i1} + r_i = x_{11} + r_1$$

which can be solved to $x_{ij} = 1 + x_{1j} + x_{i1}$; in other words defining the first row / first column defines the whole board. We can check that this condition is also sufficient to guarantee that if two squares are colored the same, then their parity is the same.

It remains to make sure that if two squares have the same parity, they are colored the same. Assume $x_{11}=1$. Then if $x_{21}$ is black, the second row is equal to the first row, so the parity of the second row is $r_2 = r_1$, and that is OK. If $x_{21}=0$, then the second row is the first row flipped, so the parity of the second row is $r_2 = a - r_1 = r_1$ (since $a$ is even). This is not OK, because $x_{21} \ne x_{11}$ should imply $r_1 \ne r_2$. Therefore the first column and first row are all black, and by using $x_{ij} = x_{1j} + x_{i1} + 1$ to fill the remaining squares they must all be black as well.

Thus the only solution is to press all buttons, as we wanted to show.