Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1997 USAMO Problems/Problem 6"
m (→‎Solution)
Line 42: Line 42:
 
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
 
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>
 
<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,
+
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>
 
<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.
 
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: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 (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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1997_USAMO_Problems/Problem_6&oldid=79292"