China Western Mathematical Olympiad

We denote the cell in the $i$-row and $j$-column of the grid as $A_{ij}$ ($i,j\in \{1,2,\dots ,n\}$).

When $n=2k$, $k\in {\mathbb{N}}^{\ast }$, we mark each $A_{ij}$ satisfying $i+j\equiv 0(\mathrm{mod}2)$ with color red (presented by shaded areas), and that satisfying $j-i\equiv 3(\mathrm{mod}4)$ and $j-i\not\equiv j+i(\mathrm{mod}4)$ with blue (presented by oblique line areas) (see Fig. 7.1).

Fig. 7.1 Fig. 7.2

In this way, we can see that every cell adjacent to a blue one is red, and there is exactly one blue cell around each red one.

Now we do the operation on each blue cell. The number in each red cell is then changed from $+1$ to $-1$, while the numbers in the remaining cells are unchanged.

Since $n$ is an even number, we can rotate the grid around its center $O$ anticlockwise by $90^{\circ }$. Then all the red cells of the rotated grid cover exactly all the cells that are not red in the original grid (see Fig. 7.2).

We do the operations again for the original grid on all the cells that are covered by blue cells of the rotated grid. Then we see that all the numbers with value $+1$ in the remaining cells of the original grid are changed to $-1$, while the numbers in the other cells are unchanged.

Therefore, when $n$ is an even number, all the numbers in the cells of the grid can be changed to $-1$ by a finite number of operations.

When $n$ is odd, we denote the number in cell $A_{ii}$ as $M_i$ ($i=1,2,\dots ,n$), and denote the number of operations on each of their adjacent cells as $x_1,x_2,\dots ,x_{n-1},y_1,y_2,\dots ,y_{n-1}$, respectively (see Fig. 7.3).

After finite operations, it is easy to see that:

Fig. 7.3

$M_1$ is changed from $+1$ to $-1$ if and only if $x_1+y_1$ is odd;

$M_2$ is changed from $+1$ to $-1$ if and only if $x_1+y_1+x_2+y_2$ is odd;

$M_3$ is changed from $+1$ to $-1$ if and only if $x_2+y_2+x_3+y_3$ is odd;

$⋮$

$M_{n-1}$ is changed from $+1$ to $-1$ if and only if $x_{n-2}+y_{n-2}+x_{n-1}+y_{n-1}$ is odd, and

$M_n$ is changed from $+1$ to $-1$ if and only if $x_{n-1}+y_{n-1}$ is odd.

Since $n$ is odd, the sum of $n$ odd numbers is still odd. Then,

$$\begin{array}{rl}& (x_1+y_1)+(x_1+y_1+x_2+y_2)+(x_2+y_2+x_3+y_3)\\ & +\cdots +(x_{n-2}+y_{n-2}+x_{n-1}+y_{n-1})+(x_{n-1}+y_{n-1})\\ & =2(x_1+x_2+\cdots +x_{n-1}+y_1+y_2+\cdots +y_{n-1})\end{array}$$

is odd. It is impossible!

Therefore, all the numbers in the cells of a given $n\times n$ grid can be changed from $+1$ to $-1$ after a finite number of operations if and only if $n$ is an even number. ​