1994 USAMO Problems/Problem 1
Let , be positive integers, no two consecutive, and let , for . Prove that, for each positive integer , the interval , contains at least one perfect square.
We want to show that the distance between and is greater than the distance between and the next perfect square following .
Given , where no are consecutive, we can put a lower bound on . This occurs when all :
Rearranging, . So, , and the distance between and is .
Also, let be the distance between and the next perfect square following . Let's look at the function for all positive integers .
When is a perfect square, it is easy to see that . Proof: Choose . .
When is not a perfect square, . Proof: Choose with . .
So, for all and for all .
Now, it suffices to show that for all .
So, and all intervals between and will contain at least one perfect square.
We see that by increasing by some amount, we simply shift our interval by a finite amount. It suffices to consider the case (since this can be inducted across all positive integers). Let . We want the smallest interval, so we have . Simple induction reveals that the ration of consecutive squares grows slower than our linear bound. We now consider sufficiently small (where ). This first happens at . By simple casework, our answer is as desired .
|1994 USAMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5|
|All USAMO Problems and Solutions|