Difference between revisions of "2007 USAMO Problems/Problem 4"
Line 70: | Line 70: | ||
== See also == | == See also == | ||
{{USAMO newbox|year=2007|num-b=3|num-a=5}} | {{USAMO newbox|year=2007|num-b=3|num-a=5}} | ||
+ | {{MAA Notice}} |
Revision as of 13:42, 4 July 2013
Problem
An animal with cells is a connected figure consisting of
equal-sized square cells.
The figure below shows an 8-cell animal.
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.
Contents
Solution
Solution 1
Let a -dino denote an animal with
or more cells.
We show by induction that an -dino with
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 , we have two cells, which are clearly not primitive.
Inductive Step: Assume any cell animal can be partitioned into two or more
-dinos.
For a given -dino, take off any four cells (call them
) to get an animal with
cells.
This can be partitioned into two or more -dinos, let's call them
and
. This means that
and
are connected.
If both and
are
-dinos or if
don't all attach to one of them, then we're done.
So assume has
cells and thus
has at least
cells, and that
are added to
. So
has
cells total.
Let denote the cell of
attached to
. There are
cells on
besides
. Thus, of the three (or less) sides of
not attached to
, one of them must have
cells by the pigeonhole principle. It then follows that we can add
,
, and the other two sides together to get an
dino, and the side of
that has
cells is also an n-dino, so we can partition the animal with
cells into two
-dinos and we're done.
Thus, our answer is cells.
Solution 2
For simplicity, let and let
be the number of squares. Let the centers of the squares be vertices, 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:
where
,
,
,
are the numbers of verticies on each branch, WLOG
. Note
.
Claim: If , then we must be able to divide the animal into two dinosaurs.
Chose a vertex,
, for which
is minimal (i.e. out of all maximal elements in a quadruple, choose the one with the least maximal element). We have that
, so
. 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 . Now move to the first point on the branch at
. We have a new quadruple
) where
.
Now consider the maximal element of that quadruple. We already have . WLOG
, then
so
, so
is the maximal element of that quadruple.
Also , so
. But that is a contradiction to the minimality of
. Therefore, we must have that
, so we have a partition of two dinosaurs.
Maximum: .
Consider a cross with each branch having
verticies. Clearly if we take partition
verticies, we remove the center, and we are not connected.
So :
.
Solution 3 (Generalization)
Turn the dinosaur into a graph (cells are vertices, adjacent cells connected by an edge) and prove this result about graphs. A connected graph with vertices, where each vertex has degree less than or equal to
, can be partitioned into connected components of sizes at least
. So then in this special case, we have
, and so
(a possible configuration of this size that works consists of a center and 4 lines of cells each of size 2006 connected to the center). We next throw out all the geometry of this situation, so that we have a completely unconstrained graph. If we prove the above-mentioned result, we can put the geometry back in later by taking the connected components that our partition gives us, then filling back all edges that have to be there due to adjacent cells. This won't change any of the problem constraints, so we can legitimately do this.
Going, now, to the case of arbitrary graphs, we WOP on the number of edges. If we can remove any edge and still have a connected graph, then we have found a smaller graph that does not obey our theorem, a contradiction due to the minimality imposed by WOP. Therefore, the only case we have to worry about is when the graph is a tree. If it's a tree, we can root the tree and consider the size of subtrees. Pick the root such that the size of the largest subtree is minimized. This minimum must be at least , otherwise the sum of the size of the subtrees is smaller than the size of the graph, which is a contradiction. Also, it must be at most
, or else pick the subtree of size greater than
and you have decreased the size of the largest subtree if you root from that vertex instead, so you have some subtree with size between
and
. Cut the edge connecting the root to that subtree, and use that as your partition.
It is easy to see that these partitions satisfy the contention of our theorem, so we are done.
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 |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.