1995 USAMO Problems

From AoPSWiki

Problems of the 1995 USAMO.

Problem 1

Let $\, p \,$ be an odd prime. The sequence $(a_n)_{n \geq 0}$ is defined as follows: $\, a_0 = 0,$ $a_1 = 1, \, \ldots, \, a_{p-2} = p-2 \,$ and, for all $\, n \geq p-1, \,$ $\, a_n \,$ is the least positive integer that does not form an arithmetic sequence of length $\, p \,$ with any of the preceding terms. Prove that, for all $\, n, \,$ $\, a_n \,$ is the number obtained by writing $\, n \,$ in base $\, p-1 \,$ and reading the result in base $\, p$ .

Solution

Problem 2

A calculator is broken so that the only keys that still work are the $\, \sin, \; \cos,$ $\tan, \; \sin^{-1}, \; \cos^{-1}, \,$ and $\, \tan^{-1} \,$ buttons. The display initially shows 0. Given any positive rational number $\, q, \,$ show that pressing some finite sequence of buttons will yield $\, q$ . Assume that the calculator does real number calculations with infinite precision. All functions are in terms of radians.

Solution

Problem 3

Given a nonisosceles, nonright triangle $\, ABC, \,$ let $\, O \,$ denote the center of its circumscribed circle, and let $\, A_1, \, B_1, \,$ and $\, C_1 \,$ be the midpoints of sides $\, BC, \, CA, \,$ and $\, AB, \,$ respectively. Point $\, A_2 \,$ is located on the ray $\, OA_1 \,$ so that $\, \triangle OAA_1 \,$ is similar to $\, \triangle OA_2A$ . Points $\, B_2 \,$ and $\, C_2 \,$ on rays $\, OB_1 \,$ and $\, OC_1, \,$ respectively, are defined similarly. Prove that lines $\, AA_2, \, BB_2, \,$ and $\, CC_2 \,$ are concurrent, i.e. these three lines intersect at a point.

Solution

Problem 4

Suppose $\, q_0, \, q_1, \, q_2, \ldots \; \,$ is an infinite sequence of integers satisfying the following two conditions:
(i) $\, m-n \,$ divides $\, q_m - q_n \,$ for $\, m > n \geq 0,$
(ii) there is a polynomial $\, P \,$ such that $\, |q_n| < P(n) \,$ for all $\, n$ .
Prove that there is a polynomial $\, Q \,$ such that $\, q_n = Q(n) \,$ for all $\, n$ .

Solution

Problem 5

Suppose that in a certain society, each pair of persons can be classified as either amicable or hostile. We shall say that each member of an amicable pair is a friend of the other, and each member of a hostile pair is a foe of the other. Suppose that the society has $\, n \,$ persons and $\, q \,$ amicable pairs, and that for every set of three persons, at least one pair is hostile. Prove that there is at least one member of the society whose foes include $\, q(1 - 4q/n^2) \,$ or fewer amicable pairs.