Difference between revisions of "2009 USAMO Problems/Problem 3"
(→Solution) |
|||
| Line 18: | Line 18: | ||
== Solution == | == Solution == | ||
| − | + | Prove (a): To prove that any chessboard polygon that can be tiled by dominoes can be done so tastefully, we will use mathematical induction. We will show that any rectangular polygon can be tiled tastefully, and then show that any polygon that can be divided into smaller rectangular polygons can also be tiled tastefully. | |
| + | |||
| + | Base case: A 1 x 1 rectangular polygon can be tiled tastefully with a single domino. | ||
| + | Induction hypothesis: Let us assume that any rectangular polygon of area n can be tiled tastefully with dominoes. | ||
| + | Induction step: Let us consider a rectangular polygon P of area n + 1. If P is already tastefully tiled, then we are done. Otherwise, there must be a vertical or horizontal domino that violates the tasteful tiling condition. Without loss of generality, let us assume that there is a vertical domino dividing P into two subpolygons P1 and P2. | ||
| + | |||
| + | Since P1 and P2 have smaller areas than P, by the induction hypothesis they can be tiled tastefully. We can then combine these tasteful tilings to obtain a tasteful tiling of P by removing the vertical domino and replacing it with two horizontal dominoes. | ||
| + | By a similar argument, if P can be divided into smaller rectangular polygons, each of which can be tiled tastefully, then P itself can be tiled tastefully. | ||
| + | |||
| + | |||
| + | |||
| + | Prove (b): To prove that a tasteful tiling is unique, we will assume the opposite: that there are two different tasteful tilings of the same polygon. | ||
| + | Let us consider the first location where the two tilings differ. WLOG, let us assume that in one tiling there is a horizontal domino and in the other tiling there is a vertical domino at this location. | ||
| + | Since the two tilings are tasteful, neither of them can have the two configurations of dominoes shown on the left in the problem statement. Therefore, the horizontal domino must be part of a larger horizontal segment of dominos, and the vertical domino must be part of a larger vertical segment of dominos. | ||
| + | Now let us consider the four sub polygons formed by the intersection of these two segments. Each of these subpolygons is a rectangular chessboard polygon, and each of them can be tiled tastefully because they are smaller than the original polygon. Therefore, we can combine these tasteful tilings to obtain a tasteful tiling of the original polygon that differs from both of the original tilings. This contradicts our assumption that the two original tilings were different. | ||
| + | Therefore, there can be no two different tasteful tilings of the same polygon, and any tasteful tiling is unique. | ||
| + | |||
| + | Not sure if my proofs make any sense, but don't attack me if it's wrong. | ||
== See also == | == See also == | ||
Revision as of 17:02, 30 March 2023
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
Prove (a): To prove that any chessboard polygon that can be tiled by dominoes can be done so tastefully, we will use mathematical induction. We will show that any rectangular polygon can be tiled tastefully, and then show that any polygon that can be divided into smaller rectangular polygons can also be tiled tastefully.
Base case: A 1 x 1 rectangular polygon can be tiled tastefully with a single domino. Induction hypothesis: Let us assume that any rectangular polygon of area n can be tiled tastefully with dominoes. Induction step: Let us consider a rectangular polygon P of area n + 1. If P is already tastefully tiled, then we are done. Otherwise, there must be a vertical or horizontal domino that violates the tasteful tiling condition. Without loss of generality, let us assume that there is a vertical domino dividing P into two subpolygons P1 and P2.
Since P1 and P2 have smaller areas than P, by the induction hypothesis they can be tiled tastefully. We can then combine these tasteful tilings to obtain a tasteful tiling of P by removing the vertical domino and replacing it with two horizontal dominoes. By a similar argument, if P can be divided into smaller rectangular polygons, each of which can be tiled tastefully, then P itself can be tiled tastefully.
Prove (b): To prove that a tasteful tiling is unique, we will assume the opposite: that there are two different tasteful tilings of the same polygon. Let us consider the first location where the two tilings differ. WLOG, let us assume that in one tiling there is a horizontal domino and in the other tiling there is a vertical domino at this location. Since the two tilings are tasteful, neither of them can have the two configurations of dominoes shown on the left in the problem statement. Therefore, the horizontal domino must be part of a larger horizontal segment of dominos, and the vertical domino must be part of a larger vertical segment of dominos. Now let us consider the four sub polygons formed by the intersection of these two segments. Each of these subpolygons is a rectangular chessboard polygon, and each of them can be tiled tastefully because they are smaller than the original polygon. Therefore, we can combine these tasteful tilings to obtain a tasteful tiling of the original polygon that differs from both of the original tilings. This contradicts our assumption that the two original tilings were different. Therefore, there can be no two different tasteful tilings of the same polygon, and any tasteful tiling is unique.
Not sure if my proofs make any sense, but don't attack me if it's wrong.
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. 
