1997 USAMO Problems/Problem 6
Suppose the sequence of nonnegative integers satisfies
for all with . Show that there exists a real number such that (the greatest integer ) for all .
Given nonnegative integers satisfying the given inequalities, let be the set of all such that . Therefore, We can rewrite this as So we know that each is an interval. We start by proving that if and are positive integers, then . To prove this, we need the following lemma.
Lemma 1: If and are positive integers, then
Proof: We prove this by induction. If , then we wish to show that . By the given lower bound, we know that Therefore, , so the hypothesis is true for . If , then we wish to prove that . By the given upper bound, we know that Therefore, , so the hypothesis is true for .
Now suppose that (2) holds for all . If , then (2) is equivalent to , which is obviously true. If , then by the division algorithm, we can write for nonnegative integers and with . Thus by applying the lower bound repeatedly (with one of the indices equal to ), we find But then as , we can apply the inductive hypothesis with and to find . Substituting this into (3), we find This proves the hypothesis for .
Suppose that . Then by the division algorithm, we can write for nonnegative integers and with . Then by applying the upper bound repeatedly (with one of the indices equal to ), we find But as , we can apply the inductive hypothesis with and , finding that . Subsituting this into (4), we find This proves the hypothesis for .
Therefore, if the hypothesis is true for all , then it must be true for all . Hence by induction, it must be true for all positive integers and .
Now suppose for the sake of contradiction that and are disjoint intervals. Without loss of generality, we may assume that precedes on the number line. Hence the upper bound of is less than or equal to the minimum value of , or rather This simplifies to . But this contradicts the statement of Lemma 1. Therefore, .
Now we claim that . We prove this by induction. By the above, we know that . Now suppose that . The intersection of two overlapping intervals of the form and is an interval of the form , where and . Therefore, by induction, we know that if the intersection of overlapping intervals is nonempty, then it must also be an interval, say If does not intersect , then as an interval, it must appear either completely before or completely after . If appears completely before , then it has a nonempty intersection with each of , , \dots, . But we also know that is a lower bound of one of the intervals, hence cannot intersect that interval, a contradiction. A similar contradiction arises if appears completely after . Therefore, Thus by induction, . So let . Then by the definition of , we know that for all , and we are done.
|1997 USAMO (Problems • Resources)|
|1 • 2 • 3 • 4 • 5 • 6|
|All USAMO Problems and Solutions|