USAMO 2007

Let $n$ be a positive integer. Define a sequence by setting $a_{1}= n$ and, for each $k > 1$ , letting $a_{k}$ be the unique integer in the range $0\leq a_{k}\leq k-1$ for which $a_{1}+a_{2}+...+a_{k}$ is divisible by $k$ . For instance, when $n = 9$ the obtained sequence is $9,1,2,0,3,3,3,...$ . Prove that for any $n$ the sequence $a_{1},a_{2},...$ eventually becomes constant.

A square grid on the Euclidean plane consists of all points $(m,n)$ , where $m$ and $n$ 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$ ?

Let $S$ be a set containing $n^{2}+n-1$ elements, for some positive integer $n$ . Suppose that the $n$ -element subsets of $S$ are partitioned into two classes. Prove that there are at least $n$ pairwise disjoint sets in the same class.

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.

Let $ABC$ be an acute triangle with $\omega,S$ , and $R$ being its incircle, circumcircle, and circumradius, respectively. Circle $\omega_{A}$ is tangent internally to $S$ at $A$ and tangent externally to $\omega$ . Circle $S_{A}$ is tangent internally to $S$ at $A$ and tangent internally to $\omega$ . Let $P_{A}$ and $Q_{A}$ denote the centers of $\omega_{A}$ and $S_{A}$ , respectively. Define points $P_{B}, Q_{B}, P_{C}, Q_{C}$ analogously. Prove that $$8P_{A}Q_{A}\cdot P_{B}Q_{B}\cdot P_{C}Q_{C}\leq R^{3} ,$$ with equality if and only if triangle $ABC$ is equilateral.