Difference between revisions of "2007 USAMO Problems/Problem 4"
(→Solution) |
(→Solution) |
||
| Line 10: | Line 10: | ||
== Solution == | == Solution == | ||
| − | |||
| − | |||
| − | |||
| − | |||
Note that for <math>8025</math>, we can use one cell with four arms of length 2006 sticking out from it. | Note that for <math>8025</math>, we can use one cell with four arms of length 2006 sticking out from it. | ||
Revision as of 21:08, 25 April 2007
Problem
An animal with 
cells is a connected figure consisting of equal-sized cells.
The figure below shows an 8-cell animal.
(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.
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 cells, one with 
cells is obtained by adjoining a new cell by making it adjacent to one or more existing cells.
Solution
Note that for 
, we can use one cell with four arms of length 2006 sticking out from it.
Let an n-dino denote an animal with 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 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.
Solution by AoPS user Calc Rulz.
| 2007 USAMO (Problems • Resources) | ||
| Preceded by Problem 3 |
Followed by Problem 5 | |
| 1 • 2 • 3 • 4 • 5 • 6 | ||
| All USAMO Problems and Solutions | ||
