IMO 2003 · Problem 5

Given \(n>2\) and reals \(x_1\le x_2\le\cdots\le x_n\), show that \[ \left(\sum_{i,j}|x_i-x_j|\right)^2 \le \frac{2}{3}(n^2-1)\sum_{i,j}(x_i-x_j)^2. \] Show that we have equality iff the sequence is an arithmetic progression.

Official text of the problem. Official problem paper (PDF)

Solution

All double sums below run over \(1\le i,j\le n\). Put \[ \mu=\frac1n\sum_{i=1}^n x_i,\qquad y_i=x_i-\mu,\qquad a_i=2i-n-1. \] Then \(\sum_i y_i=\sum_i a_i=0\), and the standard formulas for the sums of integers and their squares give \[ \sum_{i=1}^n a_i^2 =4\sum_{i=1}^n i^2-4(n+1)\sum_{i=1}^n i+n(n+1)^2 =\frac{n(n^2-1)}3. \]

Since the \(x_i\) are in nondecreasing order, \[ \sum_{i,j}|x_i-x_j| =2\sum_{i<j}(x_j-x_i) =2\sum_{i=1}^n\bigl((i-1)-(n-i)\bigr)x_i =2\sum_{i=1}^n a_i y_i. \] Here \(x_i\) occurs positively \(i-1\) times and negatively \(n-i\) times in the sum over \(i<j\); the last equality uses \(\sum_i a_i=0\).

Also, \[ \sum_{i,j}(x_i-x_j)^2 =\sum_{i,j}(y_i-y_j)^2 =2n\sum_{i=1}^n y_i^2-2\left(\sum_{i=1}^n y_i\right)^2 =2n\sum_{i=1}^n y_i^2. \] Consequently, the Cauchy–Schwarz inequality yields \[ \begin{aligned} \left(\sum_{i,j}|x_i-x_j|\right)^2 &=4\left(\sum_{i=1}^n a_i y_i\right)^2\\ &\le 4\left(\sum_{i=1}^n a_i^2\right) \left(\sum_{i=1}^n y_i^2\right)\\ &=\frac23(n^2-1)\sum_{i,j}(x_i-x_j)^2, \end{aligned} \] as required.

The only inequality used is Cauchy–Schwarz. Since \((a_1,\ldots,a_n)\) is nonzero, equality holds exactly when there is a real number \(t\) such that \[ y_i=t(2i-n-1)\qquad(1\le i\le n). \] In this case, \[ x_{i+1}-x_i=2t \] for every \(1\le i<n\), so the sequence is an arithmetic progression. Its prescribed order forces \(t\ge0\).

Conversely, if \(x_i=b+(i-1)d\) is an arithmetic progression, then \[ \mu=b+\frac{n-1}{2}d,\qquad y_i=\frac d2(2i-n-1)=\frac d2a_i, \] so equality holds in Cauchy–Schwarz and hence in the desired inequality. This includes the constant sequence \(d=0\).

The solution was checked against Evan Chen's published IMO solution notes.