2009 USAMO Problem 3

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.

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.