Difference between revisions of "1997 USAMO Problems/Problem 6"
Mathgeek2006 (talk | contribs) |
|||
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\le 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</math>, <math>I_2</math>, \dots, <math>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 == |
Revision as of 01:29, 13 July 2016
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 , , \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.
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.