# 1994 USAMO Problems/Problem 1

## Solution

Induct on $n$. When $n = 1$, we are to show that the interval $\, [s_n, s_{n + 1}) \,$ contains at least one perfect square. This interval is equivalent to $\, [k_0, k_0 + k_1) \,$ when $n = 1$. Now for some $a , a^2 \le k_0^2 < (a+1)^2$.Then it suffices to show that the minimal "distance spanned" by the interval $\, [k_0, k_0 + k_1) \,$ is greater than or equal to the maximum distance from $k_0$ to the nearest perfect square. Since the smallest element that can follow $k_0$ is $k_0 + 2$, we have to show the below. Note that we ignore the trivial case where $k_0 = a^2$, which should be mentioned.

``` $2a + 1 \le k_0 + 2$
$2a \le k_0 + 1$
$2a \le k_0 + (q + 1), where q is a member of$\{1, 2, \ldots, 2\a}\$\$ (Error compiling LaTeX. ! Missing \$ inserted.)We now prove by contradiction. Assume that
```

```  $2a > a^2 + q + 1 a^2 - 2a + (q + 1) < 0 No real roots (Discriminant < 0) =><=$
```

$Now assume that this property should be true for$\, [s_{n - 1}, s_{n}) \,$. Now to show for$\, [s_n, s_{n + 1}) \,\$, we note that an interval is defined solely by the sum of the elements in the respective sets and '''not''' on the length of the set. Thus any s_{n + 1} can be turned into an s_n by removing k_{n + 1} and adding it to k_n. The new set is now in a form to which we can apply our assumption. The same goes for s_n and s_{n - 1}. Thus we have finished the inductive argument.

Therefore etc.\$ (Error compiling LaTeX. ! Missing \$ inserted.)