Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2009 USAMO Problems/Problem 3"

(→‎Problem)
(→‎Solution)
Line 1: Line 1:
 +
== Problem ==
 +
We define a ''chessboard polygon'' to be a polygon whose sides are situated along lines of the form <math>x = a</math> or <math>y = b</math>, where <math>a</math> and <math>b</math> 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 <math>1 \times 2</math> rectangles. Finally, a ''tasteful tiling'' is one which avoids the two configurations of dominoes shown on the left below. Two tilings of a <math>3 \times 4</math> rectangle are shown; the first one is tasteful, while the second is not, due to the vertical dominoes in the upper right corner.
 +
 +
<center><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></center> 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.
 +
 
== Problem ==
 
== Problem ==
 
We define a ''chessboard polygon'' to be a polygon whose sides are situated along lines of the form <math>x = a</math> or <math>y = b</math>, where <math>a</math> and <math>b</math> 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 <math>1 \times 2</math> rectangles. Finally, a ''tasteful tiling'' is one which avoids the two configurations of dominoes shown on the left below. Two tilings of a <math>3 \times 4</math> rectangle are shown; the first one is tasteful, while the second is not, due to the vertical dominoes in the upper right corner.
 
We define a ''chessboard polygon'' to be a polygon whose sides are situated along lines of the form <math>x = a</math> or <math>y = b</math>, where <math>a</math> and <math>b</math> 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 <math>1 \times 2</math> rectangles. Finally, a ''tasteful tiling'' is one which avoids the two configurations of dominoes shown on the left below. Two tilings of a <math>3 \times 4</math> rectangle are shown; the first one is tasteful, while the second is not, due to the vertical dominoes in the upper right corner.
Line 18: Line 36:
  
 
== Solution ==
 
== 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 ''dis''tasteful, 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. <math>\blacksquare</math>
 +
 
{{solution}}
 
{{solution}}
  

Revision as of 10:13, 15 April 2023

Problem

We define a chessboard polygon to be a polygon whose sides 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.

[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]

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.

Problem

We define a chessboard polygon to be a polygon whose sides 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.

[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]

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. $\blacksquare$

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2009_USAMO_Problems/Problem_3&oldid=192095"