USA Math Olympiad (USAMO) Problems 2008

Day I

1. Prove that for each positive integer n, there are pairwise relatively prime integers k₀; k₁, ...., k_n, all strictly greater than 1, such that k₀k₁ ... k_n - 1 is the product of two consecutive integers.

2. Let ABC be an acute, scalene triangle, and let M, N, and P be the midpoints of BC, CA, and AB, respectively. Let the perpendicular bisectors of AB and AC intersect ray AM in points D and E respectively, and let lines BD and CE intersect in point F, inside of triangle ABC. Prove that points A, N, F, and P all lie on one circle.

3. Let n be a positive integer. Denote by Sn the set of points (x; y) with integer coordinates such that A path is a sequence of distinct points (x₁, y₁), (x₂, y₂), ... ,(x_l, y_l) in S_n such that, for i = 2, ...,l the distance between (x_i, y_i) and (x_i-1, y_i-1) is 1 (in other words, the points (x_i, y_i) and (x_i-1, y_i-1) are neighbors in the lattice of points with integer coordinates).

Prove that the points in S_n cannot be partitioned into fewer than n paths (a partition of S_n into m paths is a set P of m nonempty paths such that each point in S_n appears in exactly one of the m paths in P).

Day II

4. Let P be a convex polygon with n sides, n ≥3. Any set of n-3 diagonals of P that do not intersect in the interior of the polygon determine a triangulation of P into n-2 triangles. If P is regular and there is a triangulation of P consisting of only isosceles triangles, find all the possible values of n.

5. Three nonnegative real numbers r₁, r₂, r₃ are written on a blackboard. These numbers have the property that there exist integers a₁, a₂, a₃, not all zero, satisfying a₁r₁+a₂r₂+a₃r₃ = 0.

We are permitted to perform the following operation: find two numbers x, y on the blackboard with x ≤ y, then erase y and write y - x in its place. Prove that after a finite number of such operations, we can end up with at least one 0 on the blackboard.

6. At a certain mathematical conference, every pair of mathematicians are either friends orstrangers. At mealtime, every participant eats in one of two large dining rooms. Each mathematician insists upon eating in a room which contains an even number of his or her friends. Prove that the number of ways that the mathematicians may be split between the two rooms is a power of two (i.e., is of the form 2k for some positive integer k).