USAMO 2007 Problem 4 (Graph theory) An animal with $n$ cells is a connected figure consisting of $n$ equal-sized cells
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.
I think I have misinterpreted the question. dinosaur can be partitioned into 2 dinosaurs if it has more than 4014 cells so the answer is 4013 but the actual answer is 8025. What am I doing wrong?
 A: Note that animals must be connected by definition.  This is the property your argument is ignoring.
In particular,

A dinosaur can be partitioned into 2 dinosaurs if it has more than 4014 cells

is false.  It's possible you were mixing it up with its [true] converse

A dinosaur can be partitioned into 2 dinosaurs only if it has more than 4014 cells

but this by itself isn't sufficient to solve the problem.

With that in mind, it's pretty simple to find a primitive dinosaur with 8025 cells.  For instance, consider the coordinate plane with square cells of side length 1 on any point of the form $(x,0)$ or $(0,x)$ where $x$ is an integer such that $-2006 \leq x \leq 2006$.  Then any dinosaur must include the central point $(0,0)$, so there cannot be two disjoint dinosaurs.
It's a bit harder to show this is the maximum, which is where most of the proof would be.
A: Let $n>8025$ be the order of the graph associated with our dinosaur. Start with a single vertex. Iteratively build a subgraph by adding each step a vertex adjacent to your actual subgraph. If adding this vertex does not disconnect the remaining graph, it's all good. If it disconnects it, then it can create at most 3 connected graphs (without counting the actual subgraph being constructed), because the graph is of degree bounded by 3. In this case, we leave the biggest connected graph alone and add the remaining connected components to our subgraph. We continue this until our subgraph gets bigger than $2007$. Then, the remaining graph has also a size bigger than $2007$. This is because in the worst case, the last subgraph constructed before getting over $2007$ is of maximal size $2006$. When you add the adjacent vertex, you get a subgraph of size $2007$. In the worst case, the biggest connected component created is of minimal size $\lceil\frac{n-2007}{3}\rceil \geq \lceil\frac{8026-2007}{3}\rceil = 2007$
As shown by Brian Moehring, this bound is tight.
