1
$\begingroup$

Given $n \times n$ board randomly filled with $x \in \{0, 1\}$. When you invert value in cell $x_{i,j}$, all corresponding values in $row_i$ and $col_j$ are inverted too. The goal is to fill the board only with zeroes.

I solved this task a long time ago for $n = 4$ in an old game. The question is how to find a rigorous proof that a solution exists $\forall n \in \mathbb{N}$?

I started to think in the following way. We can find all solutions for $n = 2$ and all of them would require less than $3$ steps to solve. So, because of $a \oplus1 = \overline a$ (this operation actually describes each step) and the parity of the number of columns/rows, we can say that solutions exist $\forall n = 2 ^ k$, because we will be able to solve each square $2 \times 2$ independently. But it doesn't help for $n = 3$, which actually has solutions for some cases.

I created a quick example to test here.

$\endgroup$

2 Answers 2

3
$\begingroup$

I think the puzzle cannot always be solved when $n>1$ is odd. Consider the entries in the top and bottom rows. Each step flips an even number of entries (either 2 or $n+1$) in these rows. So if you start with an odd number of zeros in these rows, you cannot finish with all zeros.

If $n$ is even, I believe you can always solve the puzzle, as you can produce a sequence of steps with the net result of flipping just one entry. (A sketch as follows. First construction: Flip four times in a rectangle shape. The net result is just flipping the corners of the rectangle. Second construction: Flip two times, not using the same row or column. The result is a set of flips in the shape of a hash (#) with two intersections missing. Because $n$ is even, the non-intersection points can be partitioned into sets of 4, each 4 points making up a rectangle. Use the first construction to remove the flips in all these 4 element sets. The net result is two just flips, in different rows and columns. Third construction: One step produces flips in the shape of a plus (+). The flips not at the intersection can be partitioned into pairs, each in a different row and column. Use the second construction to remove these. The result is a single flip.)

$\endgroup$
1
  • 1
    $\begingroup$ For $n$ even, flip all entries on a fixed row and column. The net effect is that only the intersection point remains flipped. $\endgroup$ Feb 2, 2018 at 14:57
1
$\begingroup$

This is an extended comment short of a solution.

Define an $n^2\times n^2$ matrix $A_n$ with rows and columns indexed by the positions $(i,j)$. Row $(i,j)$ of the matrix is 0 except for 1 in the columns $(i,\ast)$ and $(\ast,j)$. I.e., row $(i,j)$ says what happens when you invert position $(i,j)$. Each row thus has $2n-1$ ones in it.

Now the boards that you can solve are exactly the vectors in the row space of $A_n$ over the field of 2 elements.

To show that all boards can solved, what you need is for $A_n$ to be non-singular, again over the field of 2 elements. One way would be to show that every elementary board can be solved, where an elementary board has exactly one 1. By symmetry, it will suffice to solve the board with 1 in the (1,1) position and zeros elsewhere. If that board is solvable, all boards are solvable.

Incidentally, this is a game but it isn't game theory.

$\endgroup$
5
  • $\begingroup$ For $n$ odd the matrix is singular, because of the following identities between its rows: $(1,1) + (1,2) + \cdots + (1,n) = (2,1) + (2,2) + \cdots + (2,n)$. In the language of recolorings: if we recolor all "crosses" whose centers lie in the same row, then we recolor all cells (whatever row we choose). $\endgroup$ Feb 2, 2018 at 13:02
  • $\begingroup$ And here is a recoloring of the left upper cell in the case of an even $n$: $(n,1) + (n-1,1) + \cdots + (1,1) + (1,2) + \cdots + (1,n)$. $\endgroup$ Feb 2, 2018 at 13:06
  • $\begingroup$ @IvanIzmestiev Is the rank $n-1$ in the odd case? $\endgroup$ Feb 3, 2018 at 3:39
  • $\begingroup$ I think, the rank is $(n-1)^2$ in the odd case. First, the corank is at least $2n-1$ because of those dependences (the sum of the matrix rows corresponding to any row or column of the board is a row consisting of ones). On the other hand, inside an $(n-1) \times (n-1)$ subboard we can recolor anything we want, so the rank is at least $(n-1)^2$. $\endgroup$ Feb 3, 2018 at 8:26
  • $\begingroup$ @IvanIzmestiev I meant to write $n^2-1$, but I'm sure you are correct about $(n-1)^2$. $\endgroup$ Feb 4, 2018 at 7:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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