1994 USAMO Problems/Problem 1
Contents
Problem
Let , be positive integers, no two consecutive, and let , for . Prove that, for each positive integer , the interval , contains at least one perfect square.
Solution
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.
Solution 2
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 .
See Also
1994 USAMO (Problems • Resources) | ||
Preceded by First Problem |
Followed by Problem 2 | |
1 • 2 • 3 • 4 • 5 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.