2002 IMO Shortlist Problems/A2

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

Page

Toolbox

Search