Question regarding numbers on chessboard

Question

On one square of a 5×5 chessboard, we write -1 and on the other 24 squares +1. In one move, you may reverse the signs of one a×a subsquare with a>1. My goal is to reach +1 on each square. On which squares should -1 be to reach the goal?

Please help me with this problem. I am not able to understand ´how to approach such a problem

Answer 1

Hint: use $0$ instead of $+1$, and $1$ instead of $-1$. Write the state of the board as a vector of 25 elements (reading left-to-right, top to bottom), each of which you should think of as a binary bit.

Now each possible "move" is also a 25-vector, with $1$s in the squares that get "flipped". To apply a "move", you add the move-vector to the starting vector. Your goal is to get a vector of all zeroes. So the question becomes:

Given the $16 + 9 + 4 + 1$ move vectors, let $S$ be their span (over the integers mod 2). Which vectors containing exactly one "1" are in this span?

That's a straightforward (although tedious) computation. You also don't need the four "size four block" vectors, because they're in the span of the size-two block vectors.

Answer 2

Here's another answer, although it's hard to imagine exactly how someone who hadn't seen it before would come up with it.

Let $$ A = \pmatrix{ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 0\\ 1 & 1 & 0 & 1 & 1\\ 0 & 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 & 0 }, B = \pmatrix{ 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1\\ 0 & 0 & 0 & 0 & 0\\ 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1 }, C = \pmatrix{ 0& 1 & 1& 0 & 1\\ 1& 0 & 0 & 1 & 0\\ 1& 0 & 0 & 1 & 0\\ 0& 1& 1 & 0 & 1\\ 1& 0& 0 & 1 & 0 } . $$ Define the dot product of two matrices to be the sum of all products of corresponding entries (mod 2).

Then the dot products of any 2x2 block of 1s with $A,B, C$ are all zero; the same goes for any dot product of any 3x3 blocks of 1s with $A,B,C$; the same goes for the dot product of the $5x5$ matrix of all 1s. (And 4x4s as well, but that's a consequence of 2x2s).

Thus any matrix in the span of these block matrices ALSO has zero dot-product with $A$, $B$, and $C$. But if we look at a matrix with a single 1 in the upper left corner, its dot product with $B$ is $1$...so it can't be in the span. The same argument works for every single-1 matrix except one. Look for the common "0" in A,B,C.

How'd I figure this out? I looked for a rational kernel-basis for the matrix I described in the previous answer, and then fiddled a bit mod 2. I'd already worked out matrix $A$ without that, but $B$ would have taken longer to come up with, and $C$ is just...weird. So as I said, although this is a quick-and-dirty argument, I don't see how a contest-math person would come up with it.