All the grids of a $m\times n$ chess board ($m,n\geq 3$), are colored either with red or with blue. Two adjacent grids (having a common side) are called a "good couple" if they have different colors. Suppose there are $S$ "good couples". Explain how to determine whether $S$ is odd or even. Is it prescribed by some specific color grids? Justify your answers.
Problem
Source: CWMO 2004, problem 6
Tags: induction, combinatorics unsolved, combinatorics,
21.10.2004 15:47
Quote: All the grids ... grids = squares? If yes, then for given $m$ and $n$ it ispossible that $S$ is odd and it is possible $S$ is even. Or I am missing something.
22.10.2004 15:48
The problem asked to find the conditions that determined S was odd or even. That is to say, S may be odd or even, which is determined by some conditions.
22.10.2004 16:39
I look through the Chinese version, the question is: whether S is odd or even is determined by the color of which grids? On what conditions is S odd? And on what conditions is S even?
22.10.2004 17:46
I mean we can't obtain parity of $S$ from numbers $n$ and $m$. So what kind of conditions do they want?
23.10.2004 18:04
The official solution put the chess board into three parts: Part I: four grids in corners; Part II: grids on four sides, not including four corners; Part III: other grids, which in the chess board, not on the sides. The official solution said that parity of S is determined by the coloring style of Part II. Here m and n are only demanded >= 3.
23.10.2004 18:22
Do you mean part II ? Anyway my opinion is
23.10.2004 18:34
Sorry, it is Part II.
23.10.2004 23:42
It seems that it is one part of the problem, and not the easiest one, to understand what the question is.... I agree : I hate this kind of statements. Pierre.
27.10.2004 18:55
This problem, in this case, is almost trivial: Consider the red squares. If we consider a connex figure formed of red squares, and it is not near the extremities of the board, it is easy to see it has an even number of $good\ couples$(proof by induction on number of squares in the figure). Now surround the $m \times n$ table with blue squares. Apply the property for all the red squares, then you see that only the ones on the sides and not on the corners have contributed an odd number of times to the number of $good\ couples$.
27.10.2004 18:58
DusT wrote: This problem, in this case, is almost trivial That is why no one write solution
06.07.2020 22:58
Classify all grids into three parts: the grids at the four corners (first part), the grids along the borderlines (not including the four corners, the second part) , and the other grids (the third part). We claim that the parity of $S$, or in other words whether or not it is even or odd, is determined by the colors of the grids in the second part. More specifically, when there are odd blue grids among the grids in the second part , $S$ is odd. Otherwise $S$ is even. Proof: We fill all red grids with label number $1$ and all blue grids with label number $-1$. Denote the label numbers filled in the grids in the first part by $a , b , c, d$, and those 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 denoting the product of two label numbers of the two grids on their common edge. Let $E$ be the product of all label numbers on common edges. There are $2$ adjacent grids for every grid in the first part, so its label number appears twice in $E$. There are $3$ adjacent grids for every grid in the second part, thus its label number appears three times in $E$. There are $4$ adjacent grids for every grid in the third part, thus its label number appears four times in $E$. Therefore, $E=(abcd)^2(x_1x_2\dots x_{2m+2n-8})^2(y_1y_2\dots y_{(m-2)(n-2)}^4=(x_1x_2\dots x_{2m+2n-8})^3$ If $x_1x_2\dots x_{2m+2n-8}=1$, then $E=1$, and in this case there are an even number of good couples. If $x_2x_2\dots x_{2m+2n-8}=-1$, then $E =- 1$, and in this case there are an odd number of good couples. $\square$ I believe this is also an official solution (there were two solutions presented).