USAMO 2008

Prove that for each positive integer $n$ , there are pairwise relatively prime integers $k_0,k_1,\ldots,k_n$ , all strictly greater than $1$ , such that $k_0k_1\ldots k_n-1$ is the product of two consecutive integers.

Let $ABC$ be an acute, scalene triangle, and let $M$ , $N$ , and $P$ be the midpoints of $\overline{BC}$ , $\overline{CA}$ , and $\overline{AB}$ , respectively. Let the perpendicular bisectors of $\overline{AB}$ and $\overline{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.

Let $n$ be a positive integer. Denote by $S_n$ the set of points $(x, y)$ with integer coordinates such that $$\left\lvert x\right\rvert + \left\lvert y + \frac{1}{2} \right\rvert < n.$$ A path is a sequence of distinct points $(x_1 , y_1), (x_2, y_2), \ldots, (x_\ell, y_\ell)$ in $S_n$ such that, for $i = 2, \ldots, \ell$ , 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 $\mathcal{P}$ of $m$ nonempty paths such that each point in $S_n$ appears in exactly one of the $m$ paths in $\mathcal{P}$ ).

Three nonnegative real numbers $r_1$ , $r_2$ , $r_3$ are written on a blackboard. These numbers have the property that there exist integers $a_1$ , $a_2$ , $a_3$ , not all zero, satisfying $a_1r_1 + a_2r_2 + a_3r_3 = 0$ . We are permitted to perform the following operation: find two numbers $x$ , $y$ on the blackboard with $x \le 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.