USAMO 1995

The sequence $\mathrm{a}_{0} \mathrm{a}_{1}, \mathrm{a}_{2}, \ldots$ of non-negative integers is defined as follows. The first $\mathrm{p}-1$ terms are $0,1,2,3, \ldots$, $p-2$. Then $a_{n}$ is the least positive integer so that there is no arithmetic progression of length $p$ in the first $\mathrm{n}+1$ terms. If $\mathrm{p}$ is an odd prime, show that $\mathrm{a}_{\mathrm{n}}$ is the number obtained by writing $\mathrm{n}$ in base $\mathrm{p}-1$, then treating the result as a number in base p. For example, if p is 5 , to get the 5 th term one writes 5 as 11 in base 4 , then treats this as a base 5 number to get 6 .

A trigonometric map is any one of sin, cos, tan, arcsin, arccos and arctan. Show that given any positive rational number $\mathrm{x}$, one can find a finite sequence of trigonometric maps which take 0 to $\mathrm{x}$. [So we need to show that we can always find a sequence of trigonometric maps $\mathrm{t}_{\mathrm{i}}$ so that: $\mathrm{x}_{1}=\mathrm{t}_{0}(0), \mathrm{x}_{2}=\mathrm{t}_{1}\left(\mathrm{x}_{1}\right), \ldots, \mathrm{x}_{\mathrm{n}}=\mathrm{t}_{\mathrm{n}}$. $\left.1\left(\mathrm{x}_{\mathrm{n}-1}\right), \mathrm{x}=\mathrm{t}_{\mathrm{n}}\left(\mathrm{x}_{\mathrm{n}}\right) \cdot\right]$

The circumcenter $\mathrm{O}$ of the triangle $\mathrm{ABC}$ does not lie on any side or median. Let the midpoints of $\mathrm{BC}, \mathrm{CA}$, $\mathrm{AB}$ be $\mathrm{L}, \mathrm{M}, \mathrm{N}$ respectively. Take $\mathrm{P}, \mathrm{Q}, \mathrm{R}$ on the rays $\mathrm{OL}, \mathrm{OM}, \mathrm{ON}$ respectively so that $\angle \mathrm{OPA}=\angle \mathrm{OAL}$, $\angle \mathrm{OQB}=\angle \mathrm{OBM}$ and $\angle \mathrm{ORC}=\angle \mathrm{OCN}$. Show that $\mathrm{AP}, \mathrm{BQ}$ and $\mathrm{CR}$ meet at a point.

$a_{0}, a_{1}, a_{2}, \ldots$ is an infinite sequence of integers such that $a_{n}-a_{m}$ is divisible by $n-m$ for all (unequal) $n$ and $m$. For some polynomial $\mathrm{p}(\mathrm{x})$ we have $\mathrm{p}(\mathrm{n})>\left|\mathrm{a}_{\mathrm{n}}\right|$ for all $\mathrm{n}$. Show that there is a polynomial $\mathrm{q}(\mathrm{x})$ such that $\mathrm{q}(\mathrm{n})=$ $a_{n}$ for all $n$.

A graph with $\mathrm{n}$ points and $\mathrm{k}$ edges has no triangles. Show that it has a point $\mathrm{P}$ such that there are at most $\mathrm{k}(1$ $-4 k / \mathrm{n}^{2}$ ) edges between points not joined to P (by an edge).