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 .
We will first prove by Induction on that Denote this statement by
For the Base Case let we know that;
Hence, the Base Case holds.
For the Inductive Step, suppose that holds for some we will prove that holds as well.
Assume for contradiction that doesn't hold, then we know that;
We know that since and are not consecutive, we have;
But this contradicts the Inductive Hypothesis that thus our assumption was false and the Inductive Step is complete.
Hence, we have proved that holds, and we will use to solve the original problem.
Now suppose that for some positive integer , the interval does not contain any perfect square, then we know that there must exist two perfect squares of consecutive integers, such that the smaller one is lesser than and the larger one greater than or equal to
We thus know that there exists some such that;
By Inequality 1;
Hence, we know that;
Combining this with Inequality 2 gives;
We know that since are not consecutive, hence, we have;
But this contradicts the statement which was proved earlier.
|1994 USAMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5|
|All USAMO Problems and Solutions|