Difference between revisions of "2002 IMO Shortlist Problems/A2"

Latest revision as of 16:58, 20 August 2008

Problem

Let $a_1, a_b, \ldots$ be an infinite sequence of real numbers, for which there exists a real number $c$ with $0 \le a_i \le c$ for all $i$ , such that

$|a_i - a_j | \ge \frac{1}{i+j} \mbox{ for all }i,\; j \mbox{ with } i \neq j.$

Prove that $c \ge 1$ .

Solutions

Solution 1

For some fixed value of $n$ , let $\sigma$ be the permutation of the first $n$ natural numbers such that $a_{\sigma(1)} , \ldots a_{\sigma(n)}$ is an increasing sequence. Then we have

$\begin{matrix} a_{\sigma(n)} - a_{\sigma(1)} &=\sum_{i=1}^{n-1} \left| a_{\sigma(i+1)} - a_{\sigma(i)} \right| \qquad \quad \\ &\ge\sum_{i=1}^{n-1} \frac{1}{\sigma(i+1) + \sigma(i)} \qquad (*) \end{matrix}$

Now, by the Cauchy-Schwarz Inequality, we have

$\begin{matrix} \left( \sum_{i=1}^{n-1} \frac{1}{\sigma(i+1) + \sigma(i)} \right) \left( \sum_{i=1}^{n-1} \sigma(i+1) + \sigma(i) \right) & \ge & (n-1)^2 \qquad \qquad \qquad \\ \qquad \qquad \qquad \qquad \qquad \sum_{i=1}^{n-1} \frac{1}{\sigma(i+1) + \sigma(i)} & \ge &\frac{(n-1)^2}{2 \sum_{i=1}^{n-1} (\sigma_{i}) - \sigma(1) - \sigma(n)} \\ & \ge &\frac{(n-1)^2}{n(n+1) -3} \qquad \qquad \\ & \ge &\frac{n-1}{n+3} . \qquad \qquad \qquad \quad \end{matrix}$

Thus for all $n$ , we must have

$c \ge \frac{n-1}{n+3} = 1 - \frac{4}{n+3},$

and therefore $c$ must be at least 1, Q.E.D.

Solution 2

We proceed to $(*)$ as in Solution 1. We now note that by the AM-HM Inequality,

$\begin{matrix} \sum_{i=1}^{n-1} \frac{1}{\sigma(i+1) + \sigma(i)} & \ge &\frac{(n-1)^2}{\sum_{i=1}^{n-1} \left[ \sigma(i+1) + \sigma(i) \right] } \qquad \qquad \qquad \\ & > &\frac{(n-1)^2}{\sum_{i=1}^{n-1} \left[ \sigma(i+1) + \sigma(i) \right] + \sigma(n) + \sigma(1) } \\ & = &\frac{(n-1)^2}{n(n+1)} . \qquad \qquad \qquad \qquad \qquad \quad \end{matrix}$

Thus for any $n$ , we have two $a_i$ that differ by more than $\frac{(n-1)^2}{n(n+1)}$ . But this becomes arbitrarily close to 1 as $n$ becomes arbitrarily large. Hence if we had $c < 1$ , then we could obtain a contradiction, so we conclude that $c \ge 1$ , Q.E.D.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Notes

The chief difficulty of this problem seems to be obtaining $(*)$ ; once this result has been obtained, there are many ways to conclude.

Resources

@@ Line 1: / Line 1: @@
 == Problem ==
-Let <math> \displaystyle a_1, a_b, \ldots </math> be an infinite sequence of real numbers, for which there exists a real number <math>\displaystyle c </math> with <math> \displaystyle 0 \le a_i \le c </math> for all <math> \displaystyle i </math>, such that
+Let <math>a_1, a_b, \ldots </math> be an infinite sequence of real numbers, for which there exists a real number <math>c </math> with <math>0 \le a_i \le c </math> for all <math>i </math>, such that
 <center>
@@ Line 9: / Line 9: @@
 </center>
-Prove that <math> \displaystyle c \ge 1 </math>.
+Prove that <math>c \ge 1 </math>.
 == Solutions ==
@@ Line 15: / Line 15: @@
 === Solution 1 ===
-For some fixed value of <math> \displaystyle n </math>, let <math> \displaystyle \sigma </math> be the [[permutation]] of the first <math> \displaystyle n </math> natural numbers such that <math> a_{\sigma(1)} , \ldots a_{\sigma(n)} </math> is an increasing sequence.  Then we have
+For some fixed value of <math>n </math>, let <math>\sigma </math> be the [[permutation]] of the first <math>n </math> natural numbers such that <math> a_{\sigma(1)} , \ldots a_{\sigma(n)} </math> is an increasing sequence.  Then we have
 <center>
 <math>
 \begin{matrix}
-a_{\sigma(n)} - a_{\sigma(1)} &= \displaystyle \sum_{i=1}^{n-1} \left| a_{\sigma(i+1)} - a_{\sigma(i)} \right| \qquad \quad \\
+a_{\sigma(n)} - a_{\sigma(1)} &=\sum_{i=1}^{n-1} \left| a_{\sigma(i+1)} - a_{\sigma(i)} \right| \qquad \quad \\
-&\ge \displaystyle \sum_{i=1}^{n-1} \frac{1}{\sigma(i+1) + \sigma(i)} \qquad (*)
+&\ge\sum_{i=1}^{n-1} \frac{1}{\sigma(i+1) + \sigma(i)} \qquad (*)
 \end{matrix}
 </math>
@@ Line 31: / Line 31: @@
 <math>
 \begin{matrix}
-\displaystyle \left( \sum_{i=1}^{n-1} \frac{1}{\sigma(i+1) + \sigma(i)} \right) \left( \sum_{i=1}^{n-1} \sigma(i+1) + \sigma(i) \right) & \ge & (n-1)^2 \qquad \qquad \qquad \\
+\left( \sum_{i=1}^{n-1} \frac{1}{\sigma(i+1) + \sigma(i)} \right) \left( \sum_{i=1}^{n-1} \sigma(i+1) + \sigma(i) \right) & \ge & (n-1)^2 \qquad \qquad \qquad \\
-\displaystyle \qquad \qquad \qquad \qquad \qquad \sum_{i=1}^{n-1} \frac{1}{\sigma(i+1) + \sigma(i)} & \ge & \displaystyle \frac{(n-1)^2}{\displaystyle 2 \sum_{i=1}^{n-1} (\sigma_{i}) - \sigma(1) - \sigma(n)} \\
+\qquad \qquad \qquad \qquad \qquad \sum_{i=1}^{n-1} \frac{1}{\sigma(i+1) + \sigma(i)} & \ge &\frac{(n-1)^2}{2 \sum_{i=1}^{n-1} (\sigma_{i}) - \sigma(1) - \sigma(n)} \\
-& \ge & \displaystyle \frac{(n-1)^2}{n(n+1) -3} \qquad \qquad \\
+& \ge &\frac{(n-1)^2}{n(n+1) -3} \qquad \qquad \\
-& \ge & \displaystyle \frac{n-1}{n+3} . \qquad \qquad \qquad \quad
+& \ge &\frac{n-1}{n+3} . \qquad \qquad \qquad \quad
 \end{matrix}
 </math>
 </center>
-Thus for all <math>\displaystyle n </math>, we must have
+Thus for all <math>n </math>, we must have
 <center>
@@ Line 47: / Line 47: @@
 </center>
-and therefore <math>\displaystyle c </math> must be at least 1, Q.E.D.
+and therefore <math>c </math> must be at least 1, Q.E.D.
 === Solution 2 ===
-We proceed to <math> \displaystyle (*) </math> as in Solution 1.  We now note that by the [[RMS-AM-GM-HM | AM-HM Inequality]],
+We proceed to <math>(*) </math> as in Solution 1.  We now note that by the [[RMS-AM-GM-HM | AM-HM Inequality]],
 <center>
 <math>
 \begin{matrix}
-\displaystyle \sum_{i=1}^{n-1} \frac{1}{\sigma(i+1) + \sigma(i)} & \ge & \displaystyle \frac{(n-1)^2}{\displaystyle \sum_{i=1}^{n-1} \left[ \sigma(i+1) + \sigma(i) \right] } \qquad \qquad \qquad \\
+\sum_{i=1}^{n-1} \frac{1}{\sigma(i+1) + \sigma(i)} & \ge &\frac{(n-1)^2}{\sum_{i=1}^{n-1} \left[ \sigma(i+1) + \sigma(i) \right] } \qquad \qquad \qquad \\
-& > & \displaystyle \frac{(n-1)^2}{\displaystyle \sum_{i=1}^{n-1} \left[ \sigma(i+1) + \sigma(i) \right] + \sigma(n) + \sigma(1) } \\
+& > &\frac{(n-1)^2}{\sum_{i=1}^{n-1} \left[ \sigma(i+1) + \sigma(i) \right] + \sigma(n) + \sigma(1) } \\
-& = & \displaystyle \frac{(n-1)^2}{n(n+1)} . \qquad \qquad \qquad \qquad \qquad \quad
+& = &\frac{(n-1)^2}{n(n+1)} . \qquad \qquad \qquad \qquad \qquad \quad
 \end{matrix}
 </math>
 </center>
-Thus for any <math> \displaystyle n </math>, we have two <math> \displaystyle a_i </math> that differ by more than <math>  \frac{(n-1)^2}{n(n+1)} </math>.  But this becomes arbitrarily close to 1 as <math> \displaystyle n </math> becomes arbitrarily large.  Hence if we had <math> \displaystyle c < 1 </math>, then we could obtain a contradiction, so we conclude that <math> \displaystyle c \ge 1 </math>, Q.E.D.
+Thus for any <math>n </math>, we have two <math>a_i </math> that differ by more than <math>  \frac{(n-1)^2}{n(n+1)} </math>.  But this becomes arbitrarily close to 1 as <math>n </math> becomes arbitrarily large.  Hence if we had <math>c < 1 </math>, then we could obtain a contradiction, so we conclude that <math>c \ge 1 </math>, Q.E.D.
 {{alternate solutions}}
@@ Line 69: / Line 69: @@
 == Notes ==
-The chief difficulty of this problem seems to be obtaining <math> \displaystyle (*) </math>; once this result has been obtained, there are many ways to conclude.
+The chief difficulty of this problem seems to be obtaining <math>(*) </math>; once this result has been obtained, there are many ways to conclude.
 == Resources ==
 * [[2002 IMO Shortlist Problems]]
+* [http://www.artofproblemsolving.com/Forum/viewtopic.php?t=17331 Discussion on AoPS/MathLinks]
 [[Category:Olympiad Algebra Problems]]
+[[Category:Olympiad Inequality Problems]]

Page

Toolbox

Search