Difference between revisions of "2007 USAMO Problems/Problem 4"

Latest revision as of 13:56, 30 June 2021

Problem

(Reid Barton) An animal with $n$ cells is a connected figure consisting of $n$ equal-sized square cells. ${}^1$ The figure below shows an 8-cell animal.

A dinosaur is an animal with at least 2007 cells. It is said to be primitive if its cells cannot be partitioned into two or more dinosaurs. Find with proof the maximum number of cells in a primitive dinosaur.

${}^1$ Animals are also called polyominoes. They can be defined inductively. Two cells are adjacent if they share a complete edge. A single cell is an animal, and given an animal with $n$ cells, one with $n+1$ cells is obtained by adjoining a new cell by making it adjacent to one or more existing cells.

Solutions

Solution 1

Let a $n$ -dino denote an animal with $n$ or more cells.

We show by induction that an $n$ -dino with $4n-2$ or more animal cells is not primitive. (Note: if it had more, we could just take off enough until it had $4n-2$ , which would have a partition, and then add the cells back on.)

Base Case: If $n=1$ , we have two cells, which are clearly not primitive.

Inductive Step: Assume any $4n-2$ cell animal can be partitioned into two or more $n$ -dinos.

For a given $(4n+2)$ -dino, take off any four cells (call them $w,\ x,\ y,\ z$ ) to get an animal with $4n-2$ cells.

This can be partitioned into two or more $n$ -dinos, let's call them $A$ and $B$ . This means that $A$ and $B$ are connected.

If both $A$ and $B$ are $(n+1)$ -dinos or if $w,\ x,\ y,\ z$ don't all attach to one of them, then we're done.

So assume $A$ has $n$ cells and thus $B$ has at least $3n-2$ cells, and that $w,\ x,\ y,\ z$ are added to $B$ . So $B$ has $3n+2$ cells total.

Let $C$ denote the cell of $B$ attached to $A$ . There are $3n+1$ cells on $B$ besides $C$ . Thus, of the three (or less) sides of $C$ not attached to $A$ , one of them must have $n+1$ cells by the pigeonhole principle. It then follows that we can add $A$ , $C$ , and the other two sides together to get an $(n+1)$ dino, and the side of $C$ that has $n+1$ cells is also an $n+1$ -dino, so we can partition the animal with $4n+2$ cells into two $(n+1)$ -dinos and we're done.

Thus, our answer is $4(2007) - 3 = 8025$ cells.


Example of a solution	Attempting to partition solution into $\ge 2$ dinosaurs

Solution 2

For simplicity, let $k=2007$ and let $n$ be the number of squares. Let the centers of the squares be vertices, and connect any centers of adjacent squares with edges. Suppose we have some loops. Just remove an edge in the loop. We are still connected since you can go around the other way in the loop. Now we have no loops. Each vertex can have at most 4 edges coming out of it. For each point, assign it the quadruple: $(a,b,c,d)$ where $a$ , $b$ , $c$ , $d$ are the numbers of vertices on each branch, WLOG $a\ge b\ge c\ge d$ . Note $a+b+c+d=n-1$ .

Claim: If $n=4k-2$ , then we must be able to divide the animal into two dinosaurs. Chose a vertex, $v$ , for which $a$ is minimal (i.e. out of all maximal elements in a quadruple, choose the one with the least maximal element). We have that $4a \ge a+b+c+d=4k-3$ , so $a\ge k$ . Hence we can just cut off that branch, that forms a dinosaur.

But suppose the remaining vertices do not make a dinosaur. Then we have $b+c+d+1\le k-1 \iff n-a\le k-1\iff a\ge 3k-1$ . Now move to the first point on the branch at $a$ . We have a new quadruple $p,\ q,\ r,\ b+c+d+1$ ) where $p+q+r=a-1\ge 3k-2$ .

Now consider the maximal element of that quadruple. We already have $b+c+d+1\le k-1$ . WLOG $p\ge q\ge r\ge 0$ , then $3p\ge p+q+r=a-1\ge 3k-2\implies p\ge k$ so $p>k-1=b+c+d+1$ , so $p$ is the maximal element of that quadruple.

Also $a-1=p+q+r\ge p+0+0$ , so $p<a$ . But that is a contradiction to the minimality of $a$ . Therefore, we must have that $b+c+d+1\ge k$ , so we have a partition of two dinosaurs.

Maximum: $n=4k-3$ . Consider a cross with each branch having $k-1$ verticies. Clearly if we take partition $k$ vertices, we remove the center, and we are not connected.

So $k=2007$ : $4\cdot 2007-3=8025$ .

Solution 3 (Generalization)

Turn the dinosaur into a graph (cells are vertices, adjacent cells connected by an edge) and prove this result about graphs. A connected graph with $V$ vertices, where each vertex has degree less than or equal to $D$ , can be partitioned into connected components of sizes at least $\frac{V-1}{D}$ . So then in this special case, we have $D = 4$ , and so $V = 2006 \times 4+1$ (a possible configuration of this size that works consists of a center and 4 lines of cells each of size 2006 connected to the center). We next throw out all the geometry of this situation, so that we have a completely unconstrained graph. If we prove the above-mentioned result, we can put the geometry back in later by taking the connected components that our partition gives us, then filling back all edges that have to be there due to adjacent cells. This won't change any of the problem constraints, so we can legitimately do this.

Going, now, to the case of arbitrary graphs, we WOP on the number of edges. If we can remove any edge and still have a connected graph, then we have found a smaller graph that does not obey our theorem, a contradiction due to the minimality imposed by WOP. Therefore, the only case we have to worry about is when the graph is a tree. If it's a tree, we can root the tree and consider the size of subtrees. Pick the root such that the size of the largest subtree is minimized. This minimum must be at least $\frac{V-1}{D}$ , otherwise the sum of the size of the subtrees is smaller than the size of the graph, which is a contradiction. Also, it must be at most $\frac{V}{2}$ , or else pick the subtree of size greater than $\frac{V}{2}$ and you have decreased the size of the largest subtree if you root from that vertex instead, so you have some subtree with size between $\frac{V-1}{D}$ and $\frac V2$ . Cut the edge connecting the root to that subtree, and use that as your partition.

It is easy to see that these partitions satisfy the contention of our theorem, so we are done.

Solution 4

Let $s$ denote the minimum number of cells in a dinosaur; the number this year is $s = 2007$ .

Claim: The maximum number of cells in a primitive dinosaur is $4(s - 1) + 1$ .

First, a primitive dinosaur can contain up to $4(s - 1) + 1$ cells. To see this, consider a dinosaur in the form of a cross consisting of a central cell and four arms with $s - 1$ cells apiece. No connected figure with at least $s$ cells can be removed without disconnecting the dinosaur.

The proof that no dinosaur with at least $4(s - 1) + 2$ cells is primitive relies on the following result.

Lemma. Let $D$ be a dinosaur having at least $4(s - 1) + 2$ cells, and let $R$ (red) and $B$ (black) be two complementary animals in $D$ , i.e. $R\cap B = \emptyset$ and $R\cup B = D$ . Suppose $|R|\leq s - 1$ . Then $R$ can be augmented to produce animals $\~{R}\subset R$ (Error compiling LaTeX. Unknown error_msg) and $\{B} = D\backslash\{R}$ (Error compiling LaTeX. Unknown error_msg) such that at least one of the following holds:

(i) $|\{R}|\geq s$ (Error compiling LaTeX. Unknown error_msg) and $|\~{B}|\geq s$ (Error compiling LaTeX. Unknown error_msg),

(ii) $|\{R}| = |R| + 1$ (Error compiling LaTeX. Unknown error_msg),

(iii) $|R| < |\{R}|\leq s - 1$ (Error compiling LaTeX. Unknown error_msg).

Proof. If there is a black cell adjacent to $R$ that can be made red without disconnecting $B$ , then (ii) holds. Otherwise, there is a black cell $c$ adjacent to $R$ whose removal disconnects $B$ . Of the squares adjacent to $c$ , at least one is red, and at least one is black, otherwise $B$ would be disconnected. Then there are at most three resulting components $\mathcal{C}_1, \mathcal{C}_2, \mathcal{C}_3$ of $B$ after the removal of $c$ . Without loss of generality, $\mathcal{C}_3$ is the largest of the remaining components. (Note that $\mathcal{C}_1$ or $\mathcal{C}_2$ may be empty.) Now $\mathcal{C}_3$ has at least $\lceil (3s - 2)/3\rceil = s$ cells. Let $\{B} = \mathcal{C}_3$ (Error compiling LaTeX. Unknown error_msg). Then $|\{R}| = |R| + |\mathcal{C}_1| + |\mathcal{C}_2| + 1$ (Error compiling LaTeX. Unknown error_msg). If $|\{B}|\leq 3s - 2$ (Error compiling LaTeX. Unknown error_msg), then $|\{R}|\geq s$ (Error compiling LaTeX. Unknown error_msg) and (i) holds. If $|\{B}|\geq 3s - 1$ (Error compiling LaTeX. Unknown error_msg) then either (ii) or (iii) holds, depending on whether $|\{R}|\geq s$ (Error compiling LaTeX. Unknown error_msg) or not. $\blacksquare$

Starting with $|R| = 1$ , repeatedly apply the Lemma. Because in alternatives (ii) and (iii) $|R|$ increases but remains less than $s$ , alternative (i) eventually must occur. This shows that no dinosaur with at least $4(s - 1) + 2$ cells is primitive.

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

@@ Line 1: / Line 1: @@
 == Problem ==
+(''Reid Barton'') An ''animal'' with <math>n</math> ''cells'' is a connected figure consisting of <math>n</math> equal-sized [[Square (geometry)|square]] cells.<math>{}^1</math> The figure below shows an 8-cell animal.
-An ''animal'' with <math>n</math> ''cells'' is a connected figure consisting of <math>n</math> equal-sized cells.<math>{}^1</math> The figure below shows an 8-cell animal.
+<div style="text-align:center;">[[Image:2007 USAMO-4.PNG|350px]]</div>
-(insert picture here)
+A ''dinosaur'' is an animal with at least 2007 cells.  It is said to be ''primitive'' if its cells cannot be partitioned into two or more dinosaurs.  Find with proof the [[maximum]] number of cells in a primitive dinosaur.
-A ''dinosaur'' is an animal with at least 2007 cells.  It is said to be ''primitive'' it its cells cannot be partitioned into two or more dinosaurs.  Find with proof the maximum number of cells in a primitive dinosaur.
+<small><math>{}^1</math>Animals are also called ''[[polyomino]]es''.  They can be defined [[induction|inductively]].  Two cells are ''adjacent'' if they share a complete [[edge]].  A single cell is an animal, and given an animal with <math>n</math> cells, one with <math>n+1</math> cells is obtained by adjoining a new cell by making it adjacent to one or more existing cells.</small>
-<math>{}^1</math>Animals are also called ''polyominoes''.  They can be defined inductively.  Two cells are ''adjacent'' if they share a complete edge.  A single cell is an animal, and given an animal with <math>n</math> cells, one with <math>n+1</math> cells is obtained by adjoining a new cell by making it adjacent to one or more existing cells.
+== Solutions ==
-== Solution ==
+=== Solution 1 ===
-{{solution}}
+Let a <math>n</math>-dino denote an animal with <math>n</math> or more cells.
-Note that for the dinosaur to have <math>\ge</math> 4014 cells then the answer is <math>4(2007-1)+1=8025</math>.
+We show by [[induction]] that an <math>n</math>-dino with <math>4n-2</math> or more animal cells is not primitive. (Note: if it had more, we could just take off enough until it had <math>4n-2</math>, which would have a partition, and then add the cells back on.)
-Note that for <math>8025</math>, we can use one cell with four arms of length 2006 sticking out from it.
+Base Case: If <math>n=1</math>, we have two cells, which are clearly not primitive.
-Let an n-dino denote an animal with <math>n</math> or more cells.
+Inductive Step: Assume any <math>4n-2</math> cell animal can be partitioned into two or more <math>n</math>-dinos.
-We show by induction that an n-dino with 4n-2 or more animal cells is not primitive. (Note: if it had more, we could just take off enough until it had 4n-2, which would have a partition, and then add the cells back on)
+For a given <math>(4n+2)</math>-dino, take off any four cells (call them <math>w,\ x,\ y,\ z</math>) to get an animal with <math>4n-2</math> cells.
-Base Case: If n=1, we have two boxes, which are clearly not primitive.
+This can be partitioned into two or more <math>n</math>-dinos, let's call them <math>A</math> and <math>B</math>. This means that <math>A</math> and <math>B</math> are connected.
-Inductive Step: Assume any 4n-2 cell animal can be partitioned into two or more n-dinos.
+If both <math>A</math> and <math>B</math> are <math>(n+1)</math>-dinos or if <math>w,\ x,\ y,\ z</math> don't all attach to one of them, then we're done.
-For a given 4n+2-dino, take off any four cells (call them w,x,y,z) to get an animal with 4n-2 cells.
+So assume <math>A</math> has <math>n</math> cells and thus <math>B</math> has at least <math>3n-2</math> cells, and that <math>w,\ x,\ y,\ z</math> are added to <math>B</math>. So <math>B</math> has <math>3n+2</math> cells total.
-This can be partitioned into two or more n-dinos, let's call them A and B. This means that A:B, where : denotes a connection.
+Let <math>C</math> denote the cell of <math>B</math> attached to <math>A</math>. There are <math>3n+1</math> cells on <math>B</math> besides <math>C</math>. Thus, of the three (or less) sides of <math>C</math> not attached to <math>A</math>, one of them must have <math>n+1</math> cells by the [[pigeonhole principle]]. It then follows that we can add <math>A</math>, <math>C</math>, and the other two sides together to get an <math>(n+1)</math> dino, and the side of <math>C</math> that has <math>n+1</math> cells is also an <math>n+1</math>-dino, so we can partition the animal with <math>4n+2</math> cells into two <math>(n+1)</math>-dinos and we're done.
-Well if both A and B are n+1-dinos or if w,x,y,z don't all attach to one of them, then we're done.
+Thus, our answer is <math>4(2007) - 3 = 8025</math> cells.
-So assume A has n cells and thus B has at least 3n-2 cells, and that w,x,y,z are added to B. So B has 3n+2 cells total.
+<div style="text-align:center;">
+{|
+|-
+|width="50%"|[[Image:2007 USAMO-4b.PNG|Example of a solution]]
+|width="50%"|[[Image:2007 USAMO-4c.PNG|Attempting to partition the solution into <math>\ge 2</math> dinosaurs]]
-Let C denote the cell of B attached to A. There are 3n+1 cells on B besides C. Thus, of the three sides of C not attached to A, one of them must have n+1 cells by the pigeonhole principle. It then follows that we can add A, C, and the other two sides together to get an n+1 dino, and the side of C that has n+1 cells is also an n-dino, so we can partition the animal with 4n+2 cells into two n+1-dinos and we're done.
+|-
+|width="50%"|Example of a solution
+|width="50%"|Attempting to partition solution into <math>\ge 2</math> dinosaurs
+|}
+</div>
-Solution by AoPS user Calc Rulz.
+=== Solution 2 ===
+For simplicity, let <math>k=2007</math> and let <math>n</math> be the number of [[square]]s. Let the centers of the squares be [[vertice]]s, and connect any centers of adjacent squares with edges. Suppose we have some [[loop]]s. Just remove an edge in the loop. We are still connected since you can go around the other way in the loop. Now we have no loops. Each vertex can have at most 4 edges coming out of it. For each point, assign it the [[quadruple]]: <math>(a,b,c,d)</math> where <math>a</math>, <math>b</math>, <math>c</math>, <math>d</math> are the numbers of vertices on each branch, [[WLOG]] <math>a\ge b\ge c\ge d</math>. Note <math>a+b+c+d=n-1</math>.
+Claim: If <math>n=4k-2</math>, then we must be able to divide the animal into two dinosaurs.
+Chose a vertex, <math>v</math>, for which <math>a</math> is minimal (i.e. out of all maximal elements in a quadruple, choose the one with the least maximal element).  We have that <math>4a \ge a+b+c+d=4k-3</math>, so <math>a\ge k</math>. Hence we can just cut off that branch, that forms a dinosaur.
+But suppose the remaining vertices do not make a dinosaur. Then we have <math>b+c+d+1\le k-1 \iff n-a\le k-1\iff a\ge 3k-1</math>. Now move to the first point on the branch at <math>a</math>. We have a new quadruple <math>p,\ q,\ r,\ b+c+d+1</math>) where <math>p+q+r=a-1\ge 3k-2</math>.
+Now consider the maximal element of that quadruple. We already have <math>b+c+d+1\le k-1</math>. WLOG <math>p\ge q\ge r\ge 0</math>, then <math>3p\ge p+q+r=a-1\ge 3k-2\implies p\ge k</math> so <math>p>k-1=b+c+d+1</math>, so <math>p</math> is the maximal element of that quadruple.
+Also <math>a-1=p+q+r\ge p+0+0</math>, so <math>p<a</math>. But that is a [[contradiction]] to the minimality of <math>a</math>. Therefore, we must have that <math>b+c+d+1\ge k</math>, so we have a partition of two dinosaurs.
+Maximum: <math>n=4k-3</math>.
+Consider a cross with each branch having <math>k-1</math> verticies. Clearly if we take partition <math>k</math> vertices, we remove the center, and we are not connected.
+So <math>k=2007</math>: <math>4\cdot 2007-3=8025</math>.
+=== Solution 3 (Generalization) ===
+Turn the dinosaur into a [[graph]] (cells are [[vertex|vertices]], adjacent cells connected by an edge) and prove this result about graphs. A connected graph with <math>V</math> vertices, where each vertex has degree less than or equal to <math>D</math>, can be partitioned into connected components of sizes at least <math>\frac{V-1}{D}</math>. So then in this special case, we have <math>D = 4</math>, and so <math>V = 2006 \times 4+1</math> (a possible configuration of this size that works consists of a center and 4 lines of cells each of size 2006 connected to the center). We next throw out all the [[geometry]] of this situation, so that we have a completely unconstrained graph. If we prove the above-mentioned result, we can put the geometry back in later by taking the connected components that our partition gives us, then filling back all edges that have to be there due to adjacent cells. This won't change any of the problem constraints, so we can legitimately do this.
+Going, now, to the case of arbitrary graphs, we WOP on the number of edges. If we can remove any edge and still have a connected graph, then we have found a smaller graph that does not obey our theorem, a contradiction due to the minimality imposed by WOP. Therefore, the only case we have to worry about is when the graph is a tree. If it's a tree, we can root the tree and consider the size of subtrees. Pick the root such that the size of the largest subtree is minimized. This minimum must be at least <math>\frac{V-1}{D}</math>, otherwise the sum of the size of the subtrees is smaller than the size of the graph, which is a contradiction. Also, it must be at most <math>\frac{V}{2}</math>, or else pick the subtree of size greater than <math>\frac{V}{2}</math> and you have decreased the size of the largest subtree if you root from that vertex instead, so you have some subtree with size between <math>\frac{V-1}{D}</math> and <math>\frac V2</math>. Cut the edge connecting the root to that subtree, and use that as your partition.
+It is easy to see that these partitions satisfy the contention of our theorem, so we are done.
+=== Solution 4 ===
+Let <math>s</math> denote the minimum number of cells in a dinosaur; the number this year is <math>s = 2007</math>.
+'''Claim:''' The maximum number of cells in a primitive dinosaur is <math>4(s - 1) + 1</math>.
+First, a primitive dinosaur can contain up to <math>4(s - 1) + 1</math> cells. To see this, consider a dinosaur in the form of a cross consisting of a central cell and four arms with <math>s - 1</math> cells apiece. No connected figure with at least <math>s</math> cells can be removed without disconnecting the dinosaur.
+The proof that no dinosaur with at least <math>4(s - 1) + 2</math> cells is primitive relies on the following result.
+'''Lemma.''' Let <math>D</math> be a dinosaur having at least <math>4(s - 1) + 2</math> cells, and let <math>R</math> (red) and <math>B</math> (black) be two complementary animals in <math>D</math>, i.e. <math>R\cap B = \emptyset</math> and <math>R\cup B = D</math>. Suppose <math>|R|\leq s - 1</math>. Then <math>R</math> can be augmented to produce animals <math>\~{R}\subset R</math> and <math>\{B} = D\backslash\{R}</math> such that at least one of the following holds:
+(i) <math>|\{R}|\geq s</math> and <math>|\~{B}|\geq s</math>,
+(ii) <math>|\{R}| = |R| + 1</math>,
+(iii) <math>|R| < |\{R}|\leq s - 1</math>.
+''Proof.'' If there is a black cell adjacent to <math>R</math> that can be made red without disconnecting <math>B</math>, then (ii) holds. Otherwise, there is a black cell <math>c</math> adjacent to <math>R</math> whose removal disconnects <math>B</math>. Of the squares adjacent to <math>c</math>, at least one is red, and at least one is black, otherwise <math>B</math> would be disconnected. Then there are at most three resulting components <math>\mathcal{C}_1, \mathcal{C}_2, \mathcal{C}_3</math> of <math>B</math> after the removal of <math>c</math>. Without loss of generality, <math>\mathcal{C}_3</math> is the largest of the remaining components. (Note that <math>\mathcal{C}_1</math> or <math>\mathcal{C}_2</math> may be empty.) Now <math>\mathcal{C}_3</math> has at least <math>\lceil (3s - 2)/3\rceil = s</math> cells. Let <math>\{B} = \mathcal{C}_3</math>. Then <math>|\{R}| = |R| + |\mathcal{C}_1| + |\mathcal{C}_2| + 1</math>. If <math>|\{B}|\leq 3s - 2</math>, then <math>|\{R}|\geq s</math> and (i) holds. If <math>|\{B}|\geq 3s - 1</math> then either (ii) or (iii) holds, depending on whether <math>|\{R}|\geq s</math> or not. <math>\blacksquare</math>
+Starting with <math>|R| = 1</math>, repeatedly apply the Lemma. Because in alternatives (ii) and (iii) <math>|R|</math> increases but remains less than <math>s</math>, alternative (i) eventually must occur. This shows that no dinosaur with at least <math>4(s - 1) + 2</math> cells is primitive.
+{{alternate solutions}}
+== See also ==
+* <url>viewtopic.php?t=145848 Discussion on AoPS/MathLinks</url>
 {{USAMO newbox|year=2007|num-b=3|num-a=5}}
+[[Category:Olympiad Combinatorics Problems]]
+{{MAA Notice}}

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

Page

Toolbox

Search