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

Latest revision as of 13:12, 12 April 2023

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 < 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 18: / Line 18: @@
 '''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
+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>.

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"

Latest revision as of 13:12, 12 April 2023

Problem

Solution

See Also