# 2006 USAMO Problems

## Day 1

### Problem 1

Let $\displaystyle p$ be a prime number and let $\displaystyle s$ be an integer with $\displaystyle 0 < s < p$. Prove that there exist integers $\displaystyle m$ and $\displaystyle n$ with $\displaystyle 0 < m < n < p$ and

$\left\{ \frac{sm}{p} \right\} < \left\{ \frac{sn}{p} \right\} < \frac{s}{p}$

if and only if $\displaystyle s$ is not a divisor of $\displaystyle p-1$.

Note: For $\displaystyle x$ a real number, let $\lfloor x \rfloor$ denote the greatest integer less than or equal to $x$, and let $\{x\} = x - \lfloor x \rfloor$ denote the fractional part of $\displaystyle x$.

### Problem 2

For a given positive integer $\displaystyle k$ find, in terms of $\displaystyle k$, the minimum value of $\displaystyle N$ for which there is a set of $\displaystyle 2k+1$ distinct positive integers that has sum greater than $\displaystyle N$ but every subset of size $\displaystyle k$ has sum at most $\displaystyle N/2$.

### Problem 3

For integral $\displaystyle m$, let $\displaystyle p(m)$ be the greatest prime divisor of $\displaystyle m$. By convention, we set $p(\pm 1)=1$ and $p(0)=\infty$. Find all polynomials $\displaystyle f$ with integer coefficients such that the sequence $\{ p(f(n^2))-2n) \} _{n\ge 0}$ is bounded above. (In particular, this requires $f(n^2)\neq 0$ for $n\ge 0$.)

## Day 2

### Problem 4

Find all positive integers $\displaystyle n$ such that there are $k\ge 2$ positive rational numbers $a_1,a_2,\ldots a_k$ satisfying $a_1+a_2+...+a_k = a_1 \cdot a_2 \cdot \cdots a_k = n$.

### Problem 5

A mathematical frog jumps along the number line. The frog starts at 1, and jumps according to the following rule: if the frog is at integer $\displaystyle n$, then it can jump either to $\displaystyle n+1$ or to $n+2^{m_n+1}$ where $2^{m_n}$ is the largest power of 2 that is a factor of $\displaystyle n$. Show that if $k\ge 2$ is a positive integer and $\displaystyle i$ is a nonnegative integer, then the minimum number of jumps needed to reach $\displaystyle 2^i k$ is greater than the minimum number of jumps needed to reach $\displaystyle 2^i$.

### Problem 6

Let $\displaystyle ABCD$ be a quadrilateral, and let $\displaystyle E$ and $\displaystyle F$ be points on sides $\displaystyle AD$ and $\displaystyle BC$, respectively, such that $\displaystyle AE/ED = BF/FC$. Ray $\displaystyle FE$ meets rays $\displaystyle BA$ and $\displaystyle CD$ at $\displaystyle S$ and $\displaystyle T$ respectively. Prove that the circumcircles of triangles $\displaystyle SAE, SBF, TCF,$ and $\displaystyle TDE$ pass through a common point.