China Western Mathematical Olympiad

Solution I Classify all grids into three parts: the grids at the four corners, the grids along the borderlines (not including four corners), and the other grids. Fill all red grids with label number $1$, all blue grids with label number $-1$. Denote the label numbers filled in the grids in the first part by $a$, $b$, $c$ and $d$, in the second part by $x_1,x_2,\dots ,x_{2m+2n-8}$, and in the third part by $y_1,y_2,\dots ,y_{(m-2)(n-2)}$. For any two adjacent grids we write a label number which is the product of two label numbers of the two grids on their common edge. Let $H$ be the product of all label numbers on common edges.

There are $2$ adjacent grids for every grid in the first part, thus its label number appears twice in $H$. There are $3$ adjacent grids for every grid in the second part, thus its label number appears three times in $H$. There are $4$ adjacent grids for every grid in the third part, thus its label number appears four times in $H$. Therefore, $$H=(abcd{)}^2(x_1{x}_2\cdots x_{2m+2n-8}{)}^3(y_1{y}_2\cdots y_{(m-2)(n-2)}{)}^4=(x_1{x}_2\cdots x_{2m+2n-8}{)}^3.$$ If $x_1{x}_2\cdots x_{2m+2n-8}=1$, then $H=1$, and in this case there are even good couples. If $x_1{x}_2\cdots x_{2m+2n-8}=-1$, then $H=-1$, and in this case there are odd good couples. It shows that whether $S$ is even or odd is determined by colors of the grids in the second part. Moreover, when there are odd blue grids among the grids in the second part, $S$ is odd. Otherwise $S$ is even.

Solution II Classify all grids into three parts: the grids at the four corners, the grids along the borderlines (not containing four corners), and the other grids.

If all grids are red, then $S=0$, which is even. If there are blue grids we pick any one of them, say $A$, and change $A$ into a red one. We call this changing a transformation.

(1) $A$ is a grid in the first part. Suppose that there are $k$ red grids and $2-k$ blue grids among $A$'s two adjacent grids. After changing $A$ into a red one, the number of good couples increases by $2-k-k=2-2k$. It follows that the parity even or odd of $S$ is unchanged.

(2) $A$ is a grid in the second part. Suppose that there are $p$ red grids and $3-p$ blue grids among $A$'s three adjacent grids. After changing $A$ into a red one, the number of good couples increases by $3-p-p=3-2p$. It follows that the parity of $S$ is changed.

(3) $A$ is a grid in the third part. Suppose that there are $q$ red grids and $4-q$ blue grids among $A$'s four adjacent grids. After changing $A$ into a red one, the number of good couples increases by $4-q-q=4-2q$. It follows that the parity of $S$ is unchanged.

If there are still blue grids on the chessboard after above transformation, we continue doing the transformation over and over again until no blue grid left on the chessboard. Now $S$ is changed into $0$.

Clearly, $S$ changes its parity odd times if there are odd blue grids among the second part of grids. Similarly, $S$ changes its parity even times if there are even blue grids among the second part of grids. It implies that the parity of $S$ is determined by the coloring of the second part of grids. When there exist odd blue grids among the second part of grids, $S$ is odd. When there exist even blue grids among the second part of grids, $S$ is even.