The proof goes like this for n mod 4 = 3 (also works for n mod 4 = 1):
By the construction in claim 2 we got a proper coloring for white grids. Suppose we also have a proper coloring for black grids.
Observation: If a black grid is on the boundary, then its red white neighbor is also on the boundary. This follows by the nature of the construction in claim 2.
Notice that each internal grid covers 4 grids, each non-corner boundary grid covers 3, and each corner covers 2. Also notice that at least 2 corners are white red, so the number of white grids covered by black red grids is at least larger than the black grids covered by 2. Notice that in a proper coloring each grid is covered exactly once and the # of black grids and white grids differ by 1, so we have a contradiction.
To see the last part:
internal red black (covers 4) -> neighboring red white (covers 3 or 4)
boundary red black (covers 3) -> neighboring red white (covers 2 or 3)
however, at least 2 corners are covered, so the difference is at least 2.
By the construction in claim 2 we got a proper coloring for white grids. Suppose we also have a proper coloring for black grids.
Observation: If a black grid is on the boundary, then its red white neighbor is also on the boundary. This follows by the nature of the construction in claim 2.
Notice that each internal grid covers 4 grids, each non-corner boundary grid covers 3, and each corner covers 2. Also notice that at least 2 corners are white red, so the number of white grids covered by black red grids is at least larger than the black grids covered by 2. Notice that in a proper coloring each grid is covered exactly once and the # of black grids and white grids differ by 1, so we have a contradiction.
To see the last part:
internal red black (covers 4) -> neighboring red white (covers 3 or 4)
boundary red black (covers 3) -> neighboring red white (covers 2 or 3)
however, at least 2 corners are covered, so the difference is at least 2.
选择“Disable on www.wenxuecity.com”
选择“don't run on pages on this domain”
