Crowded Interval. Topic: Inequalities/Sequences & Series. Level: Olympiad.

Problem: (2002 IMO Shortlist - A2) Let $a_1,a_2,\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}$ for all $ i,j $ with $ i \neq j $.


Prove that $c \ge 1$.

Solution: Consider the finite subsequence $ a_1, a_2, \ldots, a_n $ for some positive integer $ n $. Let $ b_1, b_2, \ldots, b_n $ be a permutation of $ 1,2,\ldots,n $ such that $ a_{b_1} < a_{b_2} < \cdots < a_{b_n} $. This makes our consecutive differences all positive, so we don't need the absolute value signs anymore.

Consider the difference $ a_{b_n}-a_{b_1} $. We know that

$ a_{b_n}-a_{b_1} = \displaystyle \sum_{k=2}^n \left(a_{b_k}-a_{b_{k-1}}\right) $.

But from the given condition we have $ a_{b_k}-a_{b_{k-1}} \ge \frac{1}{b_k+b_{k-1}} $. So

$ a_{b_n}-a_{b_1} \ge \displaystyle \sum_{k=2}^n \frac{1}{b_k+b_{k-1}} $. (1)

By AM-HM or Cauchy, we have


$ \displaystyle \sum_{k=2}^n \frac{1}{b_k+b_{k-1}} \ge \frac{(n-1)^2}{b_1+2b_2+\cdots+2b_{n-1}+b_n} $. (2)

But because $ b_1+b_2+\cdots+b_n = \frac{n(n+1)}{2} $, we have

$ b_1+2b_2+\cdots+2b_{n-1}+b_n = n(n+1)-b_1-b_n < n^2+n-2 = (n+2)(n-1) $. (3)

Substituting (3) into (2) we have

$ \displaystyle \sum_{k=2}^n \frac{1}{b_k+b_{k-1}} > \frac{(n-1)^2}{(n+2)(n-1)} = \frac{n-1}{n+2} $. (4)

Substituting (4) into (1) we have

$ a_{b_n}-a_{b_1} > \frac{n-1}{n+2} $.

But taking $ n \rightarrow \infty $, the RHS can get arbitrarily close to $ 1 $, so

$ a_{b_n}-a_{b_1} \ge 1 $

$ a_{b_n} \ge 1+a_{b_1} $.

Finally, $ a_{b_1} \ge 0 $ so $ c \ge a_{b_n} \ge 1 $ as desired. QED.

--------------------

Comment: Taking a finite subsequence of an infinite sequence can be very helpful with inequalities, because it's easier to put some sort of bound on things. Arranging the terms in increasing order also allowed us to get rid of the absolute values.

--------------------

Practice Problem: (WOOT Test 8 - #6) Determine all positive real numbers $\alpha$ satisfying the following condition:

There exists a positive integer $n$ and a finite partition $A_1, A_2, . . ., A_n$ of the set of the positive integers such that each $A_i$ is infinite and such that if $x, y \in A_i$ with $ x \neq y $, then $ |x - y| \ge \alpha^i $.