36th United States of America Mathematical Olympiad : USAMO 2007
1. Let n be a positive integer. Define a sequence by setting a1 = n and, for each k > 1, letting ak be the unique integer in the range 0 ≤ ak ≤ k – 1 for which a1 + a2 + … + ak 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 a1, a2, a3, …. eventually becomes constant.
2. 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?
3. Let S be a set containing n2 + 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.
4. An animal with n cells is a connected figure consisting of n 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 if its cells cannot be partitioned into two or more dinosaurs. Find with proof the maximum number of cells in a primitive dinosaur.
5. Prove that for every nonnegative integer n, the number 77^n + 1 is the product of at least 2n + 3 (not necessarily distinct) primes.
6. Let ABC be an acute triangle with ω, Ω and R being its incircle, circumcircle, and cir- cumradius, respectively. Circle ωA is tangent internally to Ω at A and tangent externally to ω. Circle ΩA is tangent internally to Ω at A and tangent internally to ω. Let PA and QA denote the centers of ωA and ΩA, respectively. Define points PB, QB, PC, QC analogously.
8PAQA . PBQB . PCQC ≤ R3
with equality if and only if triangle ABC is equilateral.