2009 USAMO 第 3 题

We define a chessboard polygon to be a polygon whose sides are situated along lines of the form $x = a$ or $y = b$, where $a$ and $b$ are integers. These lines divide the interior into unit squares, which are shaded alternately grey and white so that adjacent squares have different colors. To tile a chessboard polygon by dominoes is to exactly cover the polygon by non-overlapping $1 \times 2$ rectangles. Finally, a tasteful tiling is one which avoids the two configurations of dominoes shown on the left below. Two tilings of a $3 \times 4$ rectangle are shown; the first one is tasteful, while the second is not, due to the vertical dominoes in the upper right corner.

[asy] size(400); pathpen = linewidth(2.5); void chessboard(int a, int b, pair P){ for(int i = 0; i < a; ++i) for(int j = 0; j < b; ++j) if((i+j) % 2 == 1) fill(shift(P.x+i,P.y+j)*unitsquare,rgb(0.6,0.6,0.6)); D(P--P+(a,0)--P+(a,b)--P+(0,b)--cycle); } chessboard(2,2,(2.5,0));fill(unitsquare,rgb(0.6,0.6,0.6));fill(shift(1,1)*unitsquare,rgb(0.6,0.6,0.6)); chessboard(4,3,(6,0)); chessboard(4,3,(11,0)); MP("\mathrm{Distasteful\ tilings}",(2.25,3),fontsize(12)); /* draw lines */ D((0,0)--(2,0)--(2,2)--(0,2)--cycle); D((1,0)--(1,2)); D((2.5,1)--(4.5,1)); D((7,0)--(7,2)--(6,2)--(10,2)--(9,2)--(9,0)--(9,1)--(7,1)); D((8,2)--(8,3)); D((12,0)--(12,2)--(11,2)--(13,2)); D((13,1)--(15,1)--(14,1)--(14,3)); D((13,0)--(13,3)); [/asy]

a) Prove that if a chessboard polygon can be tiled by dominoes, then it can be done so tastefully.

b) Prove that such a tasteful tiling is unique.

我们将棋盘多边形定义为边沿 $x = a$ 或 $y = b$ 形式的线定位的多边形，其中 $a$ 和 $b$ 是整数。这些线将内部划分为单位方块，这些方块的阴影交替为灰色和白色，以便相邻的方块具有不同的颜色。用多米诺骨牌平铺棋盘多边形就是用不重叠的 $1 \times 2$ 矩形精确地覆盖多边形。最后，一种有品味的瓷砖可以避免左下图所示的两种多米诺骨牌配置。显示了 $3 \times 4$ 矩形的两个平铺；第一个很有品味，而第二个则不然，因为右上角有垂直的多米诺骨牌。

$$

[asy] 大小(400);路径笔=线宽(2.5); void chessboard(int a, int b,pair P){ for(int i = 0; i < a; ++i) for(int j = 0; j < b; ++j) if((i+j) % 2 == 1) fill(shift(P.x+i,P.y+j)*unitsquare,rgb(0.6,0.6,0.6)); D(P--P+(a,0)--P+(a,b)--P+(0,b)--循环)； } 棋盘(2,2,(2.5,0));填充(unitsquare,rgb(0.6,0.6,0.6));fill(shift(1,1)*unitsquare,rgb(0.6,0.6,0.6));棋盘(4,3,(6,0));棋盘(4,3,(11,0)); MP("\mathrm{令人厌恶的\瓷砖}",(2.25,3),fontsize(12)); /* 画线 */ D((0,0)--(2,0)--(2,2)--(0,2)--cycle); D((1,0)--(1,2)); D((2.5,1)--(4.5,1)); D((7,0)--(7,2)--(6,2)--(10,2)--(9,2)--(9,0)--(9,1)--(7,1))； D((8,2)--(8,3)); D((12,0)--(12,2)--(11,2)--(13,2)); D((13,1)--(15,1)--(14,1)--(14,3)); D((13,0)--(13,3)); [/asy]

$$

a) 证明如果棋盘多边形可以用多米诺骨牌平铺，那么它可以做得如此有品味。

b) 证明这种有品位的瓷砖是独一无二的。