An 'animal' with $n$ 'cells' is a connected figure consisting of $n$ equal-sized cells[1].
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.
USAMO 2007
- Phlembac Adib Hasan
- Posts:1016
- Joined:Tue Nov 22, 2011 7:49 pm
- Location:127.0.0.1
- Contact:
- Attachments
-
- Animals with 5 cells.
- Pentominoes.png (6.35KiB)Viewed 3186 times
Welcome to BdMO Online Forum. Check out Forum Guides & Rules
- asif e elahi
- Posts:185
- Joined:Mon Aug 05, 2013 12:36 pm
- Location:Sylhet,Bangladesh
Re: USAMO 2007
Please check someone this solution.
We say that a cell/animal is joined with another cell/animal if they share at least one common edge.
An animal is called 'good' if there exists no cell that is joined with a cell of it.
Let $D$ be the greatest primitive dinosaur. Now if another cell $x$ is joined with any cell of $D$,then $D$ can be divided into $2$ dinosaurs,call them $A$ and $B$ and $x\in A$.
Now $A$ has exactly $2007$ cells.Otherwise D can be divided into $2$ dinosaurs named A\{x} and $B$.
Let $A\cup {x}=C$ and $C$ has $2006$ cells.If C and B aren't joined, there exists a cell $y$ that is joined with $C$ but is not a cell of $B$.Then $D$ can be divided into $2$ dinosaurs named $C\cup\ y$ and $B$.So $C$ and $B$ must be joined.
We take a cell $z$ of $B$ that is joined with $C$.We remove $z$ and all the cells of $C$.As $C\cup {z}$ forms a dinosaur,there is no dinosaurs in the remaining cells.It's easy to see that ,there are at most $3$ good animals in the remaining cells.All of those good animals have at most $2006 cells$.And $C\cup {z}$ contains $2007$ cells.So $D$ contains at most $2006\times 3+2007=8025$ cells.
Now we construct a primitive dinosaur with $8025$ cells.Consider a $4013\times 4013$ sqaure colur the middle row and column of it black.The coloured squares form a primitive dinosaur with $8025$ cells.
We say that a cell/animal is joined with another cell/animal if they share at least one common edge.
An animal is called 'good' if there exists no cell that is joined with a cell of it.
Let $D$ be the greatest primitive dinosaur. Now if another cell $x$ is joined with any cell of $D$,then $D$ can be divided into $2$ dinosaurs,call them $A$ and $B$ and $x\in A$.
Now $A$ has exactly $2007$ cells.Otherwise D can be divided into $2$ dinosaurs named A\{x} and $B$.
Let $A\cup {x}=C$ and $C$ has $2006$ cells.If C and B aren't joined, there exists a cell $y$ that is joined with $C$ but is not a cell of $B$.Then $D$ can be divided into $2$ dinosaurs named $C\cup\ y$ and $B$.So $C$ and $B$ must be joined.
We take a cell $z$ of $B$ that is joined with $C$.We remove $z$ and all the cells of $C$.As $C\cup {z}$ forms a dinosaur,there is no dinosaurs in the remaining cells.It's easy to see that ,there are at most $3$ good animals in the remaining cells.All of those good animals have at most $2006 cells$.And $C\cup {z}$ contains $2007$ cells.So $D$ contains at most $2006\times 3+2007=8025$ cells.
Now we construct a primitive dinosaur with $8025$ cells.Consider a $4013\times 4013$ sqaure colur the middle row and column of it black.The coloured squares form a primitive dinosaur with $8025$ cells.
Re: USAMO 2007
I think $A \cup x =C$ should be $A=C \cup x$.
Other than that, it seems fine.
Other than that, it seems fine.
Please read Forum Guide and Rules before you post.
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi
Use $L^AT_EX$, It makes our work a lot easier!
Nur Muhammad Shafiullah | Mahi