# 1994 USAMO Problems/Problem 1

## Solution

Induct on . When , we are to show that the interval contains at least one perfect square. This interval is equivalent to when . Now for some .Then it suffices to show that the minimal "distance spanned" by the interval is greater than or equal to the maximum distance from to the nearest perfect square. Since the smallest element that can follow is , we have to show the below. Note that we ignore the trivial case where , which should be mentioned.

```
\{1, 2, \ldots, 2\a}$$ (Error compiling LaTeX. ! Missing $ inserted.)We now prove by contradiction. Assume that
```

\, [s_{n - 1}, s_{n}) \,\, [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.)