Difference between revisions of "1997 USAMO Problems/Problem 6"

Revision as of 01:29, 13 July 2016

Problem

Suppose the sequence of nonnegative integers $a_1,a_2,...,a_{1997}$ satisfies

$a_i+a_j \le a_{i+j} \le a_i+a_j+1$

for all $i, j \ge 1$ with $i+j \le 1997$ . Show that there exists a real number $x$ such that $a_n=\lfloor{nx}\rfloor$ (the greatest integer $\le nx$ ) for all $1 \le n \le 1997$ .

Solution

Given nonnegative integers $a_1,a_2,\dots, a_{1997}$ satisfying the given inequalities, let $I_n$ be the set of all $x$ such that $a_n=\lfloor nx\rfloor$ . Therefore, $I_n=\{x\,:\,a_n\le nx<a_n+1\}.$ We can rewrite this as $I_n=\left[\frac{a_n}{n},\frac{a_n+1}{n}\right).\tag{1}$ So we know that each $I_n$ is an interval. We start by proving that if $n$ and $k$ are positive integers, then $I_n\cap I_{k}\ne \emptyset$ . To prove this, we need the following lemma.

Lemma 1: If $n$ and $k$ are positive integers, then $na_k< k(a_n+1)\tag{2}$

Proof: We prove this by induction. If $k=1$ , then we wish to show that $na_1< a_n+1$ . By the given lower bound, we know that $a_n\ge a_{n-1}+a_1\ge (a_{n-2}+a_1)+a_1\ge \cdots \ge na_1.$ Therefore, $na_1\le a_n<a_n+1$ , so the hypothesis is true for $k=1$ . If $n=1$ , then we wish to prove that $a_k\le k(a_1+1)$ . By the given upper bound, we know that $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).$ Therefore, $a_k<ka_1+k=k(a_1+1)$ , so the hypothesis is true for $n=1$ .

Now suppose that (2) holds for all $k,n<j$ . If $k=n=j$ , then (2) is equivalent to $0<j$ , which is obviously true. If $n=j>k$ , then by the division algorithm, we can write $n=qk+r$ for nonnegative integers $q$ and $r$ with $0\le r<k$ . Thus by applying the lower bound repeatedly (with one of the indices equal to $1$ ), we find $k(a_n+1)\ge k(qa_k+a_r+1)=kqa_k+k(a_r+1).\tag{3}$ But then as $k,r<j$ , we can apply the inductive hypothesis with $n=r$ and $k=k$ to find $k(a_r+1)> ra_k$ . Substituting this into (3), we find $k(a_n+1)> kqa_k+ra_k=(kq+r)a_k=na_k.$ This proves the hypothesis for $n=j>k$ .

Suppose that $k=j>n$ . Then by the division algorithm, we can write $k=qn+r$ for nonnegative integers $q$ and $r$ with $0\le r<n$ . Then by applying the upper bound repeatedly (with one of the indices equal to $1$ ), we find $na_k\le n(qa_n+a_r+q)=nqa_n+na_r+nq.\tag{4}$ But as $n,r<j$ , we can apply the inductive hypothesis with $n=n$ and $k=r$ , finding that $na_r< r(a_n+1)$ . Subsituting this into (4), we find $na_k< nqa_n+r(a_n+1)+nq=(nq+r)(a_n+1)=k(a_n+1).$ This proves the hypothesis for $k=j>n$ .

Therefore, if the hypothesis is true for all $k,n<j$ , then it must be true for all $k,n\le j$ . Hence by induction, it must be true for all positive integers $k$ and $n$ . $\hfill\ensuremath{\square}$

Now suppose for the sake of contradiction that $I_n$ and $I_k$ are disjoint intervals. Without loss of generality, we may assume that $I_n$ precedes $I_k$ on the number line. Hence the upper bound of $I_n$ is less than or equal to the minimum value of $I_k$ , or rather $\frac{a_{n}+1}{n}\le \frac{a_k}{k}.$ This simplifies to $na_k\ge k(a_n+1)$ . But this contradicts the statement of Lemma 1. Therefore, $I_k\cap I_n\ne \emptyset$ .

Now we claim that $I_1\cap I_2\cap \cdots \cap I_{1997}\ne \emptyset$ . We prove this by induction. By the above, we know that $I_1\cap I_2\ne \emptyset$ . Now suppose that $I_1\cap I_2\cap\cdots\cap I_k\ne \emptyset$ . The intersection of two overlapping intervals of the form $[a,b)$ and $[c,d)$ is an interval of the form $[e,f)$ , where $e=\max\{a,c\}$ and $f=\min\{b,d\}$ . Therefore, by induction, we know that if the intersection of $k$ overlapping intervals is nonempty, then it must also be an interval, say $I_1\cap I_2\cap\cdots\cap I_k=[x_k,y_k).$ If $I_{k+1}$ does not intersect $[x_k,y_k)$ , then as an interval, it must appear either completely before $x_k$ or completely after $y_k$ . If $I_{k+1}$ appears completely before $x_k$ , then it has a nonempty intersection with each of $I_1$ , $I_2$ , \dots, $I_k$ . But we also know that $x_k$ is a lower bound of one of the intervals, hence $I_{k+1}$ cannot intersect that interval, a contradiction. A similar contradiction arises if $I_{k+1}$ appears completely after $y_k$ . Therefore, $I_1\cap I_2\cap\cdots\cap I_{k+1}\ne \emptyset.$ Thus by induction, $I_1\cap I_2\cap\cdots\cap I_{1997}\ne \emptyset$ . So let $x\in I_1\cap I_2\cap\cdots\cap I_{1997}$ . Then by the definition of $I_n$ , we know that $a_n=\lfloor nx\rfloor$ for all $1\le n\le 1997$ , and we are done.

@@ Line 4: / Line 4: @@
 <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>\lenx</math>) for all <math>1 \le n \le 1997</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 ==

1997 USAMO (Problems • Resources)
Preceded by Problem 5	Followed by Last Question
1 • 2 • 3 • 4 • 5 • 6
All USAMO Problems and Solutions

Page

Toolbox

Search

Difference between revisions of "1997 USAMO Problems/Problem 6"

Revision as of 01:29, 13 July 2016

Problem

Solution

See Also