USAMO 2007

For discussing Olympiad Level Combinatorics problems
User avatar
Phlembac Adib Hasan
Posts:1016
Joined:Tue Nov 22, 2011 7:49 pm
Location:127.0.0.1
Contact:
USAMO 2007

Unread post by Phlembac Adib Hasan » Sat Sep 27, 2014 12:55 pm

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.
Attachments
Pentominoes.png
Animals with 5 cells.
Pentominoes.png (6.35KiB)Viewed 3186 times
Welcome to BdMO Online Forum. Check out Forum Guides & Rules

User avatar
asif e elahi
Posts:185
Joined:Mon Aug 05, 2013 12:36 pm
Location:Sylhet,Bangladesh

Re: USAMO 2007

Unread post by asif e elahi » Mon Sep 29, 2014 7:04 pm

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.

User avatar
*Mahi*
Posts:1175
Joined:Wed Dec 29, 2010 12:46 pm
Location:23.786228,90.354974
Contact:

Re: USAMO 2007

Unread post by *Mahi* » Tue Sep 30, 2014 8:22 pm

I think $A \cup x =C$ should be $A=C \cup x$.
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

Post Reply