The Question
There is an integer in each square of an $8\times8$ chessboard. In one
move, you may choose any $4\times4$ or $3\times3$ square and add $1$
to each integer of the chosen square. Can you always get a table with
each entry divisible by (a) $2$, (b) $3$?
My Understanding
Here is my solution for (b), please verify:
The quantity $I$=$(W-B)^2$$\cdot$$(W+B)$
(mod3) remains invariant during the transformation as one of them is $0$ during the transformation process ($W$ is the sum of all numbers on white squares and $B$ of black squares) So, if initially we have $W=0,B=1$ we will always have $I = 1$ for (a) $I = (W-B)^2 – (W+B) $ (mod 2)
Best Answer
At first, note that you don't need the integers, you need only the residui modulo 2 or 3, so you operate in space (a) $\Bbb{Z}_2$ or (b) $\Bbb{Z}_3$. You can order the numbers in the chessboard to a long vector (a) $\Bbb{Z}_2^{64}$ or (b) $\Bbb{Z}_3^{64}$
Note that if you swap any two moves, it makes the same result. So you only need to keep track of how many of what kind of moves you did, regardless of their order. There are 16 4×4 squares and 25 3×3 squares, so there are 41 possible moves total. And performing the same move (a) twice (b) three times cancels out. You can orher these moves to a long vector (a) $\Bbb{Z}_2^{41}$ or (b) $\Bbb{Z}_3^{41}$.
Each move can be represented as a vector in (a) $\Bbb{Z}_2^{64}$ or (b) $\Bbb{Z}_3^{64}$. By performing the move, this vector is being added to the chessboard vector. So you can construct a matrix $M$ from these vectors, which will transform the move vectors to chessboard vectors. Its form is (a) $\Bbb{Z}_2^{64×41}$ (b) $\Bbb{Z}_3^{64×41}$.
Now let's ask: Does for any chessboard vector $c$ exist a move vector $m$ such that $Mm=c$?
This holds if and only if $M$ is surjective. It is not, because it's thin, so it's sometimes impossible to solve the puzzle. If $M$ had at least 64 colums (i.e. there were at least 64 different moves), it might be possible. You can also see that there are $2^{64}$ or $3^{64}$ states of the chessboard, but only $2^{41}$ or $3^{41}$ possible moves, so there must be many unaccessible states.