2003 IMO Problems/Problem 5

Problem

Let be a positive integer and let be real numbers. Prove that

with equality if and only if form an arithmetic sequence.

Solution

This problem needs a solution. If you have a solution for it, please help us out by adding it. \[ \text{We first make use of symmetry to rewrite the inequality as} \] \[ \left(\sum_{1\le i<j\le n}|x_i-x_j|\right)^2\le\frac{n^2-1}3<br="">\left(\sum_{1\le i<j\le n}|x_i-x_j|^2\right)<br="">\] \[ \text{WLOG that } x_1\le x_2\le\dots\le x_n \text{ and let } x_{i-1}-x_i=a_i. \] \[ \text{The inequality is equivalent to} \] \[ \left(\sum_{1\le i<j\le n}\left(a_i+\dots+a_{j-1}\right)="" \right)^2\le\frac{n^2-1}3<br="">\left(\sum_{1\le i<j\le n}\left(a_i+\dots+a_{j-1}\right)^2\right)="" <br="">\] \[ \text{for all } a_1,\dots,a_{n-1}. \text{But this can be rewritten as} \] \[ \left(\sum_{l=1}^{n-1}\sum_{j-i=l}\left(a_i+\dots+a_{j}\right) \right)^2\le\frac{n^2-1}3 \left(\sum_{l=1}^{n-1}\sum_{j-i=l}\left(a_i+\dots+a_{j}\right)^2\right) \] \text{By Cauchy-Schwarz:} \begin{align*} \left(\sum_{l=1}^{n-1}\sum_{j-i=l}\left(a_i+\dots+a_{j}\right)^2\right)\left(\sum_{l=1}^{n-1}\sum_{j-i=l}l^2\right)&\ge\left(\sum_{l=1}^{n-1}\sum_{j-i=l}l\left(a_i+\dots+a_j\right)\right)^2\\ &=\left(\sum_{l=1}^{n-1}l\sum_{j-i=l}\left(a_i+\dots+a_j\right)\right)^2 \end{align*} \text{We claim that } \[ \sum_{j-i=l}(a_i+\dots+a_j)=\sum_{j-i=(n-l)}(a_i+\dots+a_j). \] \text{Indeed, we may consider the } \text{ matrix:} \[ \left( \begin{array}{cccc} a_1 & a_2 & \dots & a_l \\ a_2 & a_3 & \dots & a_{l+1} \\ \vdots & \vdots & \ddots & \vdots\\ a_{n-l} & a_{n-l+1} & \dots & a_n \end{array} \right) \] \text{The first sum corresponds to summing the matrix row by row, and the second corresponds to summing it column by column. Thus the two sums are equal, as claimed.} \text{Hence:} \begin{align*} \left(\sum_{l=1}^{n-1}l\sum_{j-i=l}\left(a_i+\dots+a_j\right)\right)^2&=\left(\sum_{l=1}^{n-1}\frac n2\sum_{j-i=l}\left(a_i+\dots+a_j\right)\right)^2\\ &=\frac{n^2}4\left(\sum_{l=1}^{n-1}\sum_{j-i=l}\left(a_i+\dots+a_j\right)\right)^2 \end{align*} \text{We may also check that } \[ \sum_{l=1}^{n-1}\sum_{j-i=l}l^2=\sum_{l=1}^{n-1}(n-l)l^2=\frac{n^4-n^2}{12}. \] \text{Thus we have proven that } \[ \frac{n^4-n^2}{12}\left(\sum_{l=1}^{n-1}\sum_{j-i=l}\left(a_i+\dots+a_{j}\right)^2\right)\ge\frac{n^2}4\left(\sum_{l=1}^{n-1}\sum_{j-i=l}\left(a_i+\dots+a_j\right)\right)^2 \]</j\le></j\le></j\le></j\le>

See Also

2003 IMO (Problems) • Resources
Preceded by Problem 4	1 • 2 • 3 • 4 • 5 • 6	Followed by Problem 6
All IMO Problems and Solutions