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

(added solution tag, USAMO box, and category.)
m (Solution)
 
(5 intermediate revisions by 4 users not shown)
Line 2: Line 2:
 
Suppose the sequence of nonnegative integers <math>a_1,a_2,...,a_{1997}</math> satisfies  
 
Suppose the sequence of nonnegative integers <math>a_1,a_2,...,a_{1997}</math> satisfies  
  
<math>a_i+a_j\lea_{i+j}\lea_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\ge1</math> with <math>i+j\le1997</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\len\le1997</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 ==
{{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, 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 ==
{{USAMO newbox|year=1997|num-b=5|after=Last Problem}}
+
{{USAMO newbox|year=1997|num-b=5|after=Last Question}}
  
 
[[Category:Olympiad Algebra Problems]]
 
[[Category:Olympiad Algebra Problems]]
 +
{{MAA Notice}}

Latest revision as of 02:31, 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.

See Also

1997 USAMO (ProblemsResources)
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. AMC logo.png

Invalid username
Login to AoPS