文学城论坛
+A-

回复:朋友们试试这个,不知道几星

dynamic 2009-04-25 02:36:31 ( reads)

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.

跟帖(2)

dynamic

2009-04-25 02:48:44

two comments...

dynamic

2009-04-25 03:02:49

one more comment