USAMO 1994

$a_{1}, a_{2}, a_{3}, \ldots$ are positive integers such that $a_{n}>a_{n-1}+1$. Put $b_{n}=a_{1}+a_{2}+\ldots+a_{n}$. Show that there is always a square in the range $b_{n}, b_{n}+1, b_{n}+2, \ldots, b_{n+1}-1$.

The sequence $a_{1}, a_{2}, \ldots, a_{99}$ has $a_{1}=a_{3}=a_{5}=\ldots=a_{97}=1, a_{2}=a_{4}=a_{6}=\ldots=a_{98}=2$, and $a_{99}=3$. We interpret subscripts greater than 99 by subtracting 99 , so that $\mathbf{a}_{100}$ means $\mathrm{a}_{1}$ etc. An allowed move is to change the value of any one of the $a_{n}$ to another member of $\{1,2,3\}$ different from its two neighbors, $a_{n-1}$ and $a_{n+1}$. Is there a sequence of allowed moves which results in $\mathrm{a}_{\mathrm{m}}=\mathrm{a}_{\mathrm{m}+2}=\ldots=\mathrm{a}_{\mathrm{m}+96}=1, \mathrm{a}_{\mathrm{m}+1}=\mathrm{a}_{\mathrm{m}+3}=\ldots=\mathrm{a}_{\mathrm{m}+95}=2$, $\mathrm{a}_{\mathrm{m}+97}=3, \mathrm{a}_{\mathrm{n}+98}=2$ for some $\mathrm{m}$ ? [So if $\mathrm{m}=1$, we have just interchanged the values of $\mathrm{a}_{98}$ and $\mathrm{a}_{99}$.]

The hexagon $\mathrm{ABCDEF}$ has the following properties: (1) its vertices lie on a circle; (2) $\mathrm{AB}=\mathrm{CD}=\mathrm{EF}$; and (3) the diagonals $\mathrm{AD}, \mathrm{BE}, \mathrm{CF}$ meet at a point. Let $\mathrm{X}$ be the intersection of $\mathrm{AD}$ and $\mathrm{CE}$. Show that $\mathrm{CX} / \mathrm{XE}=$ $(\mathrm{AC} / \mathrm{CE})^{2}$.

$\mathrm{x}_{\mathrm{i}}$ is a infinite sequence of positive reals such that for all $\mathrm{n}, \mathrm{x}_{1}+\mathrm{x}_{2}+\ldots+\mathrm{x}_{\mathrm{n}} \geq \sqrt{ }$. Show that $\mathrm{x}_{1}{ }^{2}+\mathrm{x}_{2}{ }^{2}+\ldots+$ $\mathrm{x}_{\mathrm{n}}^{2}>(1+1 / 2+1 / 3+\ldots+1 / \mathrm{n}) / 4$ for all $\mathrm{n}$.

$\mathrm{X}$ is a set of $\mathrm{n}$ positive integers with sum $\mathrm{s}$ and product $\mathrm{p}$. Show for any integer $\mathrm{N}>=\mathrm{s}, \Sigma$ ( parity( $\mathrm{Y}$ ) ( $\mathrm{N}-$ sum(Y))Cs $)=\mathrm{p}$, where $\mathrm{aCb}$ is the binomial coefficient $\mathrm{a}!/(\mathrm{b}!(\mathrm{a}-\mathrm{b})$ ! ), the sum is taken over all subsets $\mathrm{Y}$ of $\mathrm{X}$, parity $(\mathrm{Y})=1$ if $\mathrm{Y}$ is empty or has an even number of elements, -1 if $\mathrm{Y}$ has an odd number of elements, and $\operatorname{sum}(\mathrm{Y})$ is the sum of the elements in $\mathrm{Y}$.