Usamo 2007

USAMO 2007 Day 1 Problem 1 Let be a positive integer. Define a sequence by setting and, for each , letting be the unique integer in the range for which is divisible by . For instance, when the obtained sequence is . Prove that for any the sequence eventually becomes constant. Solution

Problem 2 A square grid on the Euclidean plane consists of all points , where and are integers. Is it possible to cover all grid points by an infinite family of discs with non-overlapping interiors if each disc in the family has radius at least 5? Solution

Problem 3 Let be a set containing elements, for some positive integer . Suppose that the -element subsets of are partitioned into two classes. Prove that there are at least pairwise disjoint sets in the same class. Solution

Day 2 Problem 4 An animal with cells is a connected figure consisting of equal-sized 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 if 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

Problem 5 Prove that for every nonnegative integer , the number least (not necessarily distinct) primes.

is the product of at

Solution

Problem 6 Let be an acute triangle with , , and being its incircle, circumcircle, and circumradius, respectively. Circle is tangent internally to at and tangent externally to . Circle is tangent internally to at and tangent internally to . Let and denote the centers of and , respectively. Define points , , , analogously. Prove that with equality if and only if triangle is equilateral.

Solution 1 By the above, we have that

, and by definition, . Thus, . Also, both are integers, so . As the s form a non-increasing sequence of positive integers, they must eventually become constant. Therefore,

for some sufficiently large value of . Then , so eventually the sequence

becomes constant.

Solution 2 Let

. Since

, we have that .

Thus,

.

Since , for some integer , we can keep adding to satisfy the conditions, provided that because . Because

, the sequence must eventually become constant.

Lemma: among 3 tangent circles with radius greater than or equal to 5, one can always fit a circle with radius greater than

between those 3 circles.

Proof: Descartes' Circle Theorem states that if a is the curvature of a circle ( , positive for externally tangent, negative for internally tangent), then we have that Solving for a, we get Take the positive root, as the negative root corresponds to externally tangent circle. Now clearly, we have

, and

root/multiplying appropriately shows that , so

,

. Summing/square . Incidently,

, as desired.

For sake of contradiction, assume that we have a satisfactory placement of circles. Consider 3 circles, where there are no circles in between. By Appolonius' problem, there exists a circle tangent to externally that is between those 3 circles. Clearly, if we move together, must decrease in radius. Hence it is sufficient to consider 3 tangent circles. By lemma 1, there is always a circle of radius greater than

that lies between

. However, any

circle with must contain a lattice point. (Consider placing an unit square parallel to the gridlines in the circle.) That is a contradiction. Hence no such tiling exists.

Call an -element subset of separable if it has a subset in each class of the partition. We recursively build a set of disjoint separable subsets of : begin with empty and at each step if there is a separable subset which is disjoint from

all sets in add that set to . The process terminates when every separable subset intersects a set in . Let be the set of elements in which are not in any set in . We claim that one class contains every -element subset of . Suppose that

are elements of . Denote by the set . Note that for each , is not separable, so that and are in the same class. But then is in the same class for each — in particular, and are in the same class. But for any two sets we may construct such a sequence with equal to one and equal to the other. We are now ready to construct our disjoint sets. Suppose that . Then , so we may select disjoint -element subsets of . Then for each of the sets in , we may select a subset which is in the same class as all the subsets of , for a total of disjoint sets.

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 -dinos. For a given animal with

cell animal can be partitioned into two or more

-dino, take off any four cells (call them cells.

This can be partitioned into two or more -dinos, let's call them means that and are connected. If both and are then we're done.

-dinos or if

So assume has cells and thus has at least are added to . So has cells total.

) to get an and

. This

don't all attach to one of them, cells, and that

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 -dinos and we're done.

cells into two

Thus, our answer is

cells.

Example of a solution

Attempting to partition solution into dinosaurs

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 the maximal element of that quadruple.

, so is

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.

Solution 1 We proceed by induction. Let be primes.

. The result holds for

because

Now we assume the result holds for . Note that

is the product of

satisfies the recursion .

Since

is an odd power of , is a perfect square. Therefore is a difference of squares and thus composite, i.e. it is divisible by primes. By assumption, is divisible by primes. Thus is divisible by primes as desired.

Solution 2 Notice that

. Therefore it suffices

to show that Let

is composite.

. The expression becomes

which is the shortened form of the geometric series . This can be factored as . Since is an odd power of , is a perfect square, and so we can factor this by difference of squares. Therefore, it is composite.

Lemma:

Proof: Note and lie on since for a pair of tangent circles, the point of tangency and the two centers are collinear. Let touch

,

, and at , , and , respectively. Note . Consider an inversion, , centered at , passing through , . Since , is orthogonal to the inversion circle, so . Consider . Note that passes through and is tangent to , hence is a line that is tangent to . Furthermore, because is symmetric about , so the inversion preserves that reflective symmetry. Since it is a line that is

symmetric about , it must be perpendicular to . Likewise, the other line tangent to and perpendicular to . Let

and

(second intersection).

Let

and

(second intersection).

Evidently,

and

. We want:

by inversion. Note that between those lines is touching at

, and they are tangent to , so the distance . Drop a perpendicular from to ,

. Then

. Then

=

Note that

is

. So

. Applying the double angle formulas and , we get

End Lemma The problem becomes:

,

which is true because

, equality is when the circumcenter and

incenter coincide. As before, . Hence the inequality is true iff

, so, by symmetry, is equilateral.

Comment: It is much easier to determine by considering . We have , , , and . However, the inversion is always nice to use. This also gives an easy construction for because the tangency point is collinear with the intersection of and .