color the grids into white and black in the standard way. Here is one observation:
Claim 1. If a proper coloring exists, then the number of red grids in white is equal to that in black.
The proof is easy. It is sufficient to notice that in a valid coloring the red grids are disjoint 1*2 blocks.
Another observation is that the white grids and black grids can be decoupled. That is to say, if you can find a coloring for white grids such that each black grid has exactly one "white red" neighbor, and similarly one such coloring for black grids, then together they form a valid coloring.
Now suppose n is odd, then the four corners are of the same color, say white.
Claim 2. A valid coloring of white grids can be obtained by coloring all white grids whose coordinate satisfies x mod 2 = 0 and (x + y) mod 4 = 0.
Proof. Let (x,y) be a black grid. If x mod 2 = 0, then (x-1,y) and (x+1,y) are not red, and exactly one of (x,y-1) and (x,y+1) is red. The case where x mod 2 = 1 is similar.
Claim 3. Another valid coloring of white grids can be obtained by coloring all white grids satisfying x mod 2 = 0 and (x + y) mod 4 = 2.
Proof. Exactly the same as above.
However, the number of red white grids in claim 2 and 3 are differed by 1, contradicting claim 1.
Claim 1. If a proper coloring exists, then the number of red grids in white is equal to that in black.
The proof is easy. It is sufficient to notice that in a valid coloring the red grids are disjoint 1*2 blocks.
Another observation is that the white grids and black grids can be decoupled. That is to say, if you can find a coloring for white grids such that each black grid has exactly one "white red" neighbor, and similarly one such coloring for black grids, then together they form a valid coloring.
Now suppose n is odd, then the four corners are of the same color, say white.
Claim 2. A valid coloring of white grids can be obtained by coloring all white grids whose coordinate satisfies x mod 2 = 0 and (x + y) mod 4 = 0.
Proof. Let (x,y) be a black grid. If x mod 2 = 0, then (x-1,y) and (x+1,y) are not red, and exactly one of (x,y-1) and (x,y+1) is red. The case where x mod 2 = 1 is similar.
Claim 3. Another valid coloring of white grids can be obtained by coloring all white grids satisfying x mod 2 = 0 and (x + y) mod 4 = 2.
Proof. Exactly the same as above.
However, the number of red white grids in claim 2 and 3 are differed by 1, contradicting claim 1.
選擇“Disable on www.wenxuecity.com”
選擇“don't run on pages on this domain”
