2002 IMO Shortlist Problems/A2

Problem

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

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

Prove that $\displaystyle c \ge 1$ .

Solutions

Solution 1

For some fixed value of $\displaystyle n$ , let $\displaystyle \sigma$ be the permutation of the first $\displaystyle 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)} &= \displaystyle \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 (*) \end{matrix}$

Now, by the Cauchy-Schwarz Inequality, we have

$\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 \\ \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)} \\ & \ge & \displaystyle \frac{(n-1)^2}{n(n+1) -3} \qquad \qquad \\ & \ge & \displaystyle \frac{n-1}{n+3} . \qquad \qquad \qquad \quad \end{matrix}$

Thus for all $\displaystyle n$ , we must have

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

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

Solution 2

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

$\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 \\ & > & \displaystyle \frac{(n-1)^2}{\displaystyle \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 \end{matrix}$

Thus for any $\displaystyle n$ , we have two $\displaystyle a_i$ that differ by more than $\frac{(n-1)^2}{n(n+1)}$ . But this becomes arbitrarily close to 1 as $\displaystyle n$ becomes arbitrarily large. Hence if we had $\displaystyle c < 1$ , then we could obtain a contradiction, so we conclude that $\displaystyle 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 $\displaystyle (*)$ ; once this result has been obtained, there are many ways to conclude.

Resources

Page

Toolbox

Search