# 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.

===============================================

Sol:

a)
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.

b)
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.