Difference between revisions of "1997 USAMO Problems/Problem 6"
Mathgeek2006 (talk | contribs) m (→Solution) |
m |
||
Line 18: | Line 18: | ||
'''Proof:''' We prove this by induction. If <math>k=1</math>, then we wish to show that <math>na_1< a_n+1</math>. By the given lower bound, we know that | '''Proof:''' We prove this by induction. If <math>k=1</math>, then we wish to show that <math>na_1< a_n+1</math>. By the given lower bound, we know that | ||
<cmath>a_n\ge a_{n-1}+a_1\ge (a_{n-2}+a_1)+a_1\ge \cdots \ge na_1.</cmath> | <cmath>a_n\ge a_{n-1}+a_1\ge (a_{n-2}+a_1)+a_1\ge \cdots \ge na_1.</cmath> | ||
− | Therefore, <math>na_1\le a_n<a_n+1</math>, so the hypothesis is true for <math>k=1</math>. If <math>n=1</math>, then we wish to prove that <math>a_k | + | Therefore, <math>na_1\le a_n<a_n+1</math>, so the hypothesis is true for <math>k=1</math>. If <math>n=1</math>, then we wish to prove that <math>a_k < k(a_1+1)</math>. By the given upper bound, we know that |
<cmath>a_k\le a_{k-1}+(a_1+1)\le (a_{k-2}+(a_1+1))+(a_1+1)\le\cdots\le ka_1+(k-1).</cmath> | <cmath>a_k\le a_{k-1}+(a_1+1)\le (a_{k-2}+(a_1+1))+(a_1+1)\le\cdots\le ka_1+(k-1).</cmath> | ||
Therefore, <math>a_k<ka_1+k=k(a_1+1)</math>, so the hypothesis is true for <math>n=1</math>. | Therefore, <math>a_k<ka_1+k=k(a_1+1)</math>, so the hypothesis is true for <math>n=1</math>. |
Latest revision as of 14:12, 12 April 2023
Problem
Suppose the sequence of nonnegative integers satisfies
for all with
. Show that there exists a real number
such that
(the greatest integer
) for all
.
Solution
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
. 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.
See Also
1997 USAMO (Problems • Resources) | ||
Preceded by Problem 5 |
Followed by Last Question | |
1 • 2 • 3 • 4 • 5 • 6 | ||
All USAMO Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.