2009 USAMO Problem 3

I found a different solution to the second part of this problem.

We define a chessboard polygon to be a polygon whose edges 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.

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.



There must be an upper right corner of the polygon \(P\). If it's white, cover it with a vertical domino and then tile the rest by induction. Otherwise cover it with a horizontal. It is clear that this domino doesn't form distasteful tiling with the rest.

Suppose there are two different tasteful tilings, then they form a chain surrounding a non-empty chessboard polygon \(R\) with a tasteful tiling because of induction. We show that walking counterclockwise along the perimeter of such surrounded \(R\) we can always find a domino with B following W, which we call bad domino, and making one of the tilings distasteful. This is proved by induction. Given any surrounded tasteful tiling with at least a bad domino, we will prove that adding any other domino does not decrease the number of bad dominoes. Suppose the bad domino is W above B somewhere locally rightmost in \(R\). The new domino covers either W or B to its right, but not both as that'd be distasteful. However no matter what the new domino will be bad, which concludes the proof.

post by Shen-Fu Tsai