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 "2007 USAMO Problems/Problem 4"

(→‎Solution)
(images to come)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
 +
An ''animal'' with <math>n</math> ''cells'' is a connected figure consisting of <math>n</math> equal-sized [[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'' it 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.
+
__TOC__
 +
== Solution ==
 +
=== Solution 1 ===
 +
Let a <math>n</math>-dino denote an animal with <math>n</math> or more cells.
  
−
== Solution 1 ==
+
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 4n-2, 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.
 
  
−
Let an n-dino denote an animal with <math>n</math> or more cells.
+
Base Case: If <math>\displaystyle n=1</math>, we have two boxes, which are clearly not primitive.
  
−
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)
+
Inductive Step: Assume any <math>4n-2</math> cell animal can be partitioned into two or more <math>n</math>-dinos.
  
−
Base Case: If n=1, we have two boxes, which are clearly not primitive.
+
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.
  
−
Inductive Step: Assume any 4n-2 cell animal can be partitioned into two or more n-dinos.
+
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:B</math>, where : denotes a connection.
  
−
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.
+
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.
  
−
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.
+
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.
  
−
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.
+
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 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 n-dino, so we can partition the animal with <math>4n+2</math> cells into two <math>n+1</math>-dinos and 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.
+
Thus, our answer is <math>\displaystyle 4(2006) + 1 = 8025</math> cells.
  
−
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.
+
=== Solution 2 ===
−
 
 
−
Solution by AoPS user Calc Rulz.
 
−
 
 
−
== Solution 2 ==
 
  
 
For simplicity, let <math>k=2007</math> and let <math>n</math> be the number of squares. Let the centers of the squares be verticies, 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: <math>(a,b,c,d)</math> where <math>a</math>, <math>b</math>, <math>c</math>, <math>d</math> are the numbers of verticies on each branch, wlog <math>a\ge b\ge c\ge d</math>. Note <math>a+b+c+d=n-1</math>.  
 
For simplicity, let <math>k=2007</math> and let <math>n</math> be the number of squares. Let the centers of the squares be verticies, 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: <math>(a,b,c,d)</math> where <math>a</math>, <math>b</math>, <math>c</math>, <math>d</math> are the numbers of verticies on each branch, wlog <math>a\ge b\ge c\ge d</math>. Note <math>a+b+c+d=n-1</math>.  
Line 50: Line 49:
 
So <math>k=2007</math>: <math>4*2007-3=8025</math>.
 
So <math>k=2007</math>: <math>4*2007-3=8025</math>.
  
−
Solution by AoPS user Altheman.
+
== See also ==
−
 
 
−
 
 
−
 
 
 
{{USAMO newbox|year=2007|num-b=3|num-a=5}}
 
{{USAMO newbox|year=2007|num-b=3|num-a=5}}

Revision as of 16:09, 26 April 2007

Problem

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.

2007 USAMO-4.PNG

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.

${}^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.

Solution

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 $\displaystyle n=1$, we have two boxes, 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:B$, where : denotes a connection.

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 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.

Thus, our answer is $\displaystyle 4(2006) + 1 = 8025$ cells.

Solution 2

For simplicity, let $k=2007$ and let $n$ be the number of squares. Let the centers of the squares be verticies, 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 verticies 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 verticies 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$ verticies, we remove the center, and we are not connected.

So $k=2007$: $4*2007-3=8025$.

See also

2007 USAMO (Problems • Resources)
Preceded by
Problem 3 		Followed by
Problem 5
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2007_USAMO_Problems/Problem_4&oldid=14741"