Difference between revisions of "1997 USAMO Problems/Problem 6"
m |
|||
(2 intermediate revisions by one other user not shown) | |||
Line 4: | Line 4: | ||
<math>a_i+a_j \le a_{i+j} \le a_i+a_j+1</math> | <math>a_i+a_j \le a_{i+j} \le a_i+a_j+1</math> | ||
− | for all <math>i, j \ge 1</math> with <math>i+j \le 1997</math>. Show that there exists a real number <math>x</math> such that <math>a_n=\lfloor{nx}\rfloor</math> (the greatest integer <math>\ | + | for all <math>i, j \ge 1</math> with <math>i+j \le 1997</math>. Show that there exists a real number <math>x</math> such that <math>a_n=\lfloor{nx}\rfloor</math> (the greatest integer <math>\le nx</math>) for all <math>1 \le n \le 1997</math>. |
== Solution == | == Solution == | ||
− | {{ | + | Given nonnegative integers <math>a_1,a_2,\dots, a_{1997}</math> satisfying the given inequalities, let <math>I_n</math> be the set of all <math>x</math> such that <math>a_n=\lfloor nx\rfloor</math>. Therefore, |
+ | <cmath>I_n=\{x\,:\,a_n\le nx<a_n+1\}.</cmath> | ||
+ | We can rewrite this as | ||
+ | <cmath>I_n=\left[\frac{a_n}{n},\frac{a_n+1}{n}\right).\tag{1}</cmath> | ||
+ | So we know that each <math>I_n</math> is an interval. We start by proving that if <math>n</math> and <math>k</math> are positive integers, then <math>I_n\cap I_{k}\ne \emptyset</math>. To prove this, we need the following lemma. | ||
+ | |||
+ | '''Lemma 1:''' If <math>n</math> and <math>k</math> are positive integers, then | ||
+ | <cmath>na_k< k(a_n+1)\tag{2}</cmath> | ||
+ | |||
+ | '''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> | ||
+ | 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> | ||
+ | Therefore, <math>a_k<ka_1+k=k(a_1+1)</math>, so the hypothesis is true for <math>n=1</math>. | ||
+ | |||
+ | Now suppose that (2) holds for all <math>k,n<j</math>. If <math>k=n=j</math>, then (2) is equivalent to <math>0<j</math>, which is obviously true. If <math>n=j>k</math>, then by the division algorithm, we can write <math>n=qk+r</math> for nonnegative integers <math>q</math> and <math>r</math> with <math>0\le r<k</math>. Thus by applying the lower bound repeatedly (with one of the indices equal to <math>1</math>), we find | ||
+ | <cmath>k(a_n+1)\ge k(qa_k+a_r+1)=kqa_k+k(a_r+1).\tag{3}</cmath> | ||
+ | But then as <math>k,r<j</math>, we can apply the inductive hypothesis with <math>n=r</math> and <math>k=k</math> to find <math>k(a_r+1)> ra_k</math>. Substituting this into (3), we find | ||
+ | <cmath>k(a_n+1)> kqa_k+ra_k=(kq+r)a_k=na_k.</cmath> | ||
+ | This proves the hypothesis for <math>n=j>k</math>. | ||
+ | |||
+ | Suppose that <math>k=j>n</math>. Then by the division algorithm, we can write <math>k=qn+r</math> for nonnegative integers <math>q</math> and <math>r</math> with <math>0\le r<n</math>. Then by applying the upper bound repeatedly (with one of the indices equal to <math>1</math>), we find | ||
+ | <cmath>na_k\le n(qa_n+a_r+q)=nqa_n+na_r+nq.\tag{4}</cmath> | ||
+ | But as <math>n,r<j</math>, we can apply the inductive hypothesis with <math>n=n</math> and <math>k=r</math>, finding that <math>na_r< r(a_n+1)</math>. Subsituting this into (4), we find | ||
+ | <cmath>na_k< nqa_n+r(a_n+1)+nq=(nq+r)(a_n+1)=k(a_n+1).</cmath> | ||
+ | This proves the hypothesis for <math>k=j>n</math>. | ||
+ | |||
+ | Therefore, if the hypothesis is true for all <math>k,n<j</math>, then it must be true for all <math>k,n\le j</math>. Hence by induction, it must be true for all positive integers <math>k</math> and <math>n</math>. <math>\hfill\ensuremath{\square}</math> | ||
+ | |||
+ | Now suppose for the sake of contradiction that <math>I_n</math> and <math>I_k</math> are disjoint intervals. Without loss of generality, we may assume that <math>I_n</math> precedes <math>I_k</math> on the number line. Hence the upper bound of <math>I_n</math> is less than or equal to the minimum value of <math>I_k</math>, or rather | ||
+ | <cmath>\frac{a_{n}+1}{n}\le \frac{a_k}{k}.</cmath> | ||
+ | This simplifies to <math>na_k\ge k(a_n+1)</math>. But this contradicts the statement of Lemma 1. Therefore, <math>I_k\cap I_n\ne \emptyset</math>. | ||
+ | |||
+ | Now we claim that <math>I_1\cap I_2\cap \cdots \cap I_{1997}\ne \emptyset</math>. We prove this by induction. By the above, we know that <math>I_1\cap I_2\ne \emptyset</math>. Now suppose that <math>I_1\cap I_2\cap\cdots\cap I_k\ne \emptyset</math>. The intersection of two overlapping intervals of the form <math>[a,b)</math> and <math>[c,d)</math> is an interval of the form <math>[e,f)</math>, where <math>e=\max\{a,c\}</math> and <math>f=\min\{b,d\}</math>. Therefore, by induction, we know that if the intersection of <math>k</math> overlapping intervals is nonempty, then it must also be an interval, say | ||
+ | <cmath>I_1\cap I_2\cap\cdots\cap I_k=[x_k,y_k).</cmath> | ||
+ | If <math>I_{k+1}</math> does not intersect <math>[x_k,y_k)</math>, then as an interval, it must appear either completely before <math>x_k</math> or completely after <math>y_k</math>. If <math>I_{k+1}</math> appears completely before <math>x_k</math>, then it has a nonempty intersection with each of <math>I_1, I_2, \dots, I_k</math>. But we also know that <math>x_k</math> is a lower bound of one of the intervals, hence <math>I_{k+1}</math> cannot intersect that interval, a contradiction. A similar contradiction arises if <math>I_{k+1}</math> appears completely after <math>y_k</math>. Therefore, | ||
+ | <cmath>I_1\cap I_2\cap\cdots\cap I_{k+1}\ne \emptyset.</cmath> | ||
+ | Thus by induction, <math>I_1\cap I_2\cap\cdots\cap I_{1997}\ne \emptyset</math>. So let <math>x\in I_1\cap I_2\cap\cdots\cap I_{1997}</math>. Then by the definition of <math>I_n</math>, we know that <math>a_n=\lfloor nx\rfloor</math> for all <math>1\le n\le 1997</math>, and we are done. | ||
== See Also == | == See Also == |
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.