2009 USAMO Problems/Problem 3
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.
![[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]](http://latex.artofproblemsolving.com/4/b/9/4b990288de8124d702038b22187c64a70b82fd76.png)
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
NOTE: this only covers part (a).
First, tile the board in any way. This tiling may be tasteful or distasteful. If it is tasteful, we are done. But if it is distasteful, look for the distasteful 2x2 arrays in the shape. Then, if the dominoes are vertical, make them horizontal, and they will now be tasteful. If they are horizontal, make them vertical, and they too will now be tasteful. 
This problem needs a solution. If you have a solution for it, please help us out by adding it.
See also
| 2009 USAMO (Problems • Resources) | ||
| Preceded by Problem 2 |
Followed by Problem 4 | |
| 1 • 2 • 3 • 4 • 5 • 6 | ||
| All USAMO Problems and Solutions | ||
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 
