2009 USAMO Problems/Problem 3

From AoPSWiki

Problem

We define a chessboard polygon to be a polygon whose sides are situated along lines of the form or , where and 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 rectangles. Finally, a tasteful tiling is one which avoids the two configurations of dominoes shown on the left below. Two tilings of a 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.

Solution

See also

2009 USAMO (Problems • Resources: AoPS | ML)
Preceded by Problem 2	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 4