Difference between revisions of "2002 USAMO Problems/Problem 6"

Latest revision as of 16:33, 16 July 2014

Problem

I have an $n \times n$ sheet of stamps, from which I've been asked to tear out blocks of three adjacent stamps in a single row or column. (I can only tear along the perforations separating adjacent stamps, and each block must come out of the sheet in one piece.) Let $b(n)$ be the smallest number of blocks I can tear out and make it impossible to tear out any more blocks. Prove that there are real constants $c$ and $d$ such that

$\dfrac{1}{7} n^2 - cn \leq b(n) \leq \dfrac{1}{5} n^2 + dn$

for all $n > 0$ .

Solution

The upper bound requires an example of a set of $\frac{1}{5}n^2 + dn$ blocks whose removal makes it impossible to remove any further blocks. It suffices to show that we can tile the plane by tiles containing one block for every five stamps such that no more blocks can be chosen. Two such tilings are shown below with one tile outlined in heavy lines. Given an $n\times n$ section of the tiling take all blocks lying entirely within that section and add as many additional blocks as possible. If the basic tile is contained in an $(m + 1)\times (m + 1)$ square, then the $n\times n$ section is covered by tiles contained in a concentric $(n + 2m)\times (n + 2m)$ square. Hence there are at most $\frac{1}{5}(n + 2m)^2$ blocks entirely within the section. For an $n\times n$ section of the tiling, there are at most $4n$ blocks which lie partially in and partially out of that section (hence these blocks contain at most $8n$ stamps in the $n\times n$ square) and each of the additional blocks must contain one of these stamps. Thus there are at most $8n$ additional blocks. Thus there are at most $\frac{1}{5}(n + 2m)^2 + 8n\leq \frac{1}{5}n^2 + \frac{4m^2 + 4m + 40}{5}n$ blocks total.

The lower bound requires an argument. Suppose that we have a set of $b(n)$ blocks whose removal makes removing any further blocks impossible.

Solution 1

There are $2n(n - 2)$ potential blocks of three consecutive stamps in a row or column. Each of these must meet at least one of the $b(n)$ blocks removed. Conversely, each of the $b(n)$ blocks removed meets at most 14 of these potential blocks (5 oriented the same way, including itself, and 9 oriented the orthogonal way). Therefore $14b(n)\geq 2n(n - 2)$ or $b(n)\geq\frac{1}{7}n^2 - \frac{2}{7}n.$

Solution 2

Call a stamp used if it belongs to one of the $b(n)$ removed blocks. Consider the $(n - 2)^2$ five-stamp crosses centered at each stamp not on an edge of the sheet. Each cross must contain two used stamps. (One stamp not in the center is not enough to prevent another block from being torn out, and it is impossible to use one stamp in the center and use no other stamps in the cross.) In addition, each block not lying along an edge of the sheet lies entirely inside one cross, which thus contains three used stamps. There are at most $4n/3$ of the $b(n)$ blocks lying along the edges, hence there are at least $b(n) - 4n/3$ crosses containing three used stamps.

Now count the number of pairs of a used stamp and a cross containing that stamp, in two ways. First counting block by block, we get $3b(n)$ used stamps, and each used stamp is contained in at most five crosses (exactly five if it is not on an edge), for a total of at most $15b(n)$ pairs. Next, counting cross by cross, each of the $(n - 2)^2$ crosses contains at least two used stamps and we have at least $b(n) - 4n/3$ crosses containing three used stamps, for a total of at least $2(n - 2)^2 + b(n) - 4n/3$ pairs. Therefore $15b(n)\geq 2(n - 2)^2 + b(n) - \frac{4n}{3},$ or $b(n)\geq\frac{1}{7}n^2 - \frac{16}{21}n.$

Solution 3

Call a stamp used if it belongs to one of the $b(n)$ removed blocks. Count the number of pairs consisting of a used stamp and an adjacent unused stamp, in two ways.

There are at least $(n - 2)^2 - 3b(n)$ unused stamps which are not on an edge. Since no more blocks can be torn out, either the stamp to the left or right and either the stamp or below such an unused stamp must be used. Thus we have at least $2n^2 - 8n - 6b(n)$ such pairs.

Each block removed is adjacent to at most eight other stamps. However these eight stamps contain two blocks of three consecutive stamps. Hence at most six of these eight stamps can be unused. Thus each of the $b(n)$ blocks removed is involved in at most six pairs. Thus there are at most $6b(n)$ pairs.

Combining these we have $6b(n)\geq 2n^2 - 8n - 6b(n),$ or $b(n)\geq\frac{1}{6}n^2 - \frac{2}{3}n.$

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

@@ Line 3: / Line 3: @@
 I have an <math>n \times n</math> sheet of stamps, from which I've been asked to tear out blocks of three adjacent stamps in a single row or column. (I can only tear along the perforations separating adjacent stamps, and each block must come out of the sheet in one piece.) Let <math>b(n)</math> be the smallest number of blocks I can tear out and make it impossible to tear out any more blocks. Prove that there are real constants <math>c</math> and <math>d</math> such that <center><math>\dfrac{1}{7} n^2 - cn \leq b(n) \leq \dfrac{1}{5} n^2 + dn</math></center> for all <math>n > 0</math>.
-== Solutions ==
+== Solution ==
-{{solution}}
+The upper bound requires an example of a set of <math>\frac{1}{5}n^2 + dn</math> blocks whose removal makes it impossible to remove any further blocks. It suffices to show that we can tile the plane by tiles containing one block for every five stamps such that no more blocks can be chosen. Two such tilings are shown below with one tile outlined in heavy lines. Given an <math>n\times n</math> section of the tiling take all blocks lying entirely within that section and add as many additional blocks as possible. If the basic tile is contained in an <math>(m + 1)\times (m + 1)</math> square, then the <math>n\times n</math> section is covered by tiles contained in a concentric <math>(n + 2m)\times (n + 2m)</math> square. Hence there are at most <math>\frac{1}{5}(n + 2m)^2</math> blocks entirely within the section. For an <math>n\times n</math> section of the tiling, there are at most <math>4n</math> blocks which lie partially in and partially out of that section (hence these blocks contain at most <math>8n</math> stamps in the <math>n\times n</math> square) and each of the additional blocks must contain one of these stamps. Thus there are at most <math>8n</math> additional blocks. Thus there are at most
+<cmath>\frac{1}{5}(n + 2m)^2 + 8n\leq \frac{1}{5}n^2 + \frac{4m^2 + 4m + 40}{5}n</cmath>
+blocks total.
+<center>[[File:2002usamo6-1.png]]</center>
+The lower bound requires an argument. Suppose that we have a set of <math>b(n)</math> blocks whose removal makes removing any further blocks impossible.
+=== Solution 1 ===
+There are <math>2n(n - 2)</math> potential blocks of three consecutive stamps in a row or column. Each of these must meet at least one of the <math>b(n)</math> blocks removed. Conversely, each of the <math>b(n)</math> blocks removed meets at most 14 of these potential blocks (5 oriented the same way, including itself, and 9 oriented the orthogonal way). Therefore <math>14b(n)\geq 2n(n - 2)</math> or
+<cmath>b(n)\geq\frac{1}{7}n^2 - \frac{2}{7}n.</cmath>
+=== Solution 2 ===
+Call a stamp used if it belongs to one of the <math>b(n)</math> removed blocks. Consider the <math>(n - 2)^2</math> five-stamp crosses centered at each stamp not on an edge of the sheet. Each cross must contain two used stamps. (One stamp not in the center is not enough to prevent another block from being torn out, and it is impossible to use one stamp in the center and use no other stamps in the cross.) In addition, each block not lying along an edge of the sheet lies entirely inside one cross, which thus contains three used stamps. There are at most <math>4n/3</math> of the <math>b(n)</math> blocks lying along the edges, hence there are at least <math>b(n) - 4n/3</math> crosses containing three used stamps.
+Now count the number of pairs of a used stamp and a cross containing that stamp, in two ways. First counting block by block, we get <math>3b(n)</math> used stamps, and each used stamp is contained in at most five crosses (exactly five if it is not on an edge), for a total of at most <math>15b(n)</math> pairs. Next, counting cross by cross, each of the <math>(n - 2)^2</math> crosses contains at least two used stamps and we have at least <math>b(n) - 4n/3</math> crosses containing three used stamps, for a total of at least <math>2(n - 2)^2 + b(n) - 4n/3</math> pairs. Therefore
+<cmath>15b(n)\geq 2(n - 2)^2 + b(n) - \frac{4n}{3},</cmath>
+or
+<cmath>b(n)\geq\frac{1}{7}n^2 - \frac{16}{21}n.</cmath>
+=== Solution 3 ===
+Call a stamp used if it belongs to one of the <math>b(n)</math> removed blocks. Count the number of pairs consisting of a used stamp and an adjacent unused stamp, in two ways.
+There are at least <math>(n - 2)^2 - 3b(n)</math> unused stamps which are not on an edge. Since no more blocks can be torn out, either the stamp to the left or right and either the stamp or below such an unused stamp must be used. Thus we have at least <math>2n^2 - 8n - 6b(n)</math> such pairs.
+Each block removed is adjacent to at most eight other stamps. However these eight stamps contain two blocks of three consecutive stamps. Hence at most six of these eight stamps can be unused. Thus each of the <math>b(n)</math> blocks removed is involved in at most six pairs. Thus there are at most <math>6b(n)</math> pairs.
+Combining these we have
+<cmath>6b(n)\geq 2n^2 - 8n - 6b(n),</cmath>
+or
+<cmath>b(n)\geq\frac{1}{6}n^2 - \frac{2}{3}n.</cmath>
+{{alternate solutions}}
 == See also ==

2002 USAMO (Problems • Resources)
Preceded by Problem 5	Followed by Last question
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

Page

Toolbox

Search