2003 IMO Problem 5

[sourav das]

Let all $x_i$ are real for all $i=1,2,...,n$ and $x_i \geq x_j$ if and only if $i\geq j$
(a)
Prove that $\left ( \sum_{i,j=1}^{n}\left | x_i-x_j \right | \right )^2\leq \frac{2(n^2-1)}{3}\sum_{i,j=1}^{n}\left ( x_i-x_j \right )^2$
(b)
Prove that equality holds if and only if $\{x_i\}$ is an arithmetic progression .

Comment: 100th post

[sourav das]

I'm also posting my solution. If there is
any bug; please inform me.

Define $a_i = \left | x_{i+1}-x_i \right |$ Then $\left | x_{i+j}-x_{i} \right |=\left | x_{i+j}-x_{i+j-1} \right |+\left | x_{i+j-1}-x_{i+j-2}\right |+..+\left | x_{i+1}-x_{i} \right | $
$=\sum_{k=i}^{i+j-1}a_k$
By simplifying our given inequality we can find out that
\[\left ( \sum_{i,j=1}^{n}\left | x_i-x_j \right | \right )^2\leq\frac{2\left ( n^2-1 \right )}{3} \sum_{i,j=1}^{n}(x_i-x_j)^2\]\[\Leftrightarrow \left ( \sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\left | x_j-x_i \right | \right )^2\leq\frac{\left ( n^2-1 \right )}{3} \left ( \sum_{i=1}^{n-1}\sum_{j=i+1}^{n}(x_j-x_i)^2 \right )\]
\[\Leftrightarrow \left ( \sum_{i=1}^{n-1}\sum_{j=i+1}^{n}\sum_{k=i}^{j-1}a_k \right )^2\leq \left ( \frac{n^2-1}{3} \right )\left ( \sum_{i=1}^{n-1}a_i^2 +\sum_{i=1}^{n-2}(a_i+a_{i+1})^2+..(a_1+a_2+..+a_{n-1})^2 \right )\]
Sorry but now i'm jumping to:
\[\Leftrightarrow \left ( \sum_{i=1}^{n-1}a_i i(n-i) \right )^2\leq \frac{n^2-1}{3} \left ( \sum_{n-1}^{i}a_i^2i(n-i) \right )+ \frac{n^2-1}{3} \sum_{i=1}^{n-2}\sum_{j=i+1}^{n-1} 2a_i a_j i(n-j)\]
(Although i've calculate these correctly)
Again a big jump to

$\Leftrightarrow \sum_{i=1}^{n-2}\sum_{j=i+1}^{n-1}\{2a_i a_j(ij(n-i)(n-j)-\frac{n^2-1}{3}i(n-j))\}\leq $

$ \sum_{i=1}^{n-1}a_i^2( \left ( \frac{n^2-1}{3} \right )i(n-i)-i^2(n-i)^2)$

Now by A.M-G.M:

$\sum_{i=1}^{n-2}\sum_{j=i+1}^{n-1}\{2a_i a_j(ij(n-i)(n-j)-\frac{n^2-1}{3}i(n-j))\}\leq$

$ \sum_{i=1}^{n-2}\sum_{j=i+1}^{n-1}(a_i^2+a_j^2)(ij(n-i)(n-j)-\frac{n^2-1}{3}i(n-j))\}$

Now the ultimate jump of the calculations:

$\sum_{i=1}^{n-1}a_i^2( \left ( \frac{n^2-1}{3} \right )i(n-i)-i^2(n-i)^2)=\sum_{j=1}^{i-1}a_i^2\left ( ij(n-i)

(n-j)-\left ( \frac{n^2-1}{3} \right )j(n-i) \right )+$

$\sum_{j=i+1}^{n-1}a_i^2\left ( ij(n-i)(n-j)-\left ( \frac{n^2-1}{3} \right )i(n-j) \right )$

Because of A.M-G.M equality holds if and only if all $a_i$ are same which means $\{x_i\}$ is an arithmetic
progression.

I wish i could show you my calculations... But i've justified my calculations.

[*Mahi*]

Well, the problem statement says , equality appears when $\{x_i\}$ is an arithmetic progression so I think that the first move should consist of Cauchy Schwarz . Though , the solution here appears alright, and so congratulations for completing such a tedious one!

[sourav das]

Well, the problem statement says , equality appears when $\{x_i\}$ is an arithmetic progression so I think that the first move should consist of Cauchy Schwarz .

Tell me Mahi, how can you assume using any specific kind of tactics at the very beginning? Please give us an example. And this question is for all who have a lot of experience in solving problems. Let's discuss and restart to solve this problem with our discussion.It'll help us all to learn choosing tactics. (I'm still a learner of solving problems )

[FahimFerdous]

I completely agree with Sourav. So Mahi, please tell how you started thinking about the first step.

[sourav das]

Is it because of Cauchy-Schwarz equality condition has similarity with the difference between two elements of an arithmetic progression?

[*Mahi*]

You got it, all I tried was multiplying different arithmetic progression with $\sum_{i,j=1}^{n}\left ( | x_i-x_j | \right )^2$, first with easy ones like $\sum 1$ and then others, which you can find out. And trying well known techniques sometimes has it's benefits too.
I'm a learner too , so we should all try together!

[sourav das]

Mahi, Fahim, any progress? For using Cauchy-Schwarz inequality we need product of two sum of square sequences. But since in our left side, there are terms which are not square. Confusing....

[*Mahi*]

Mahi, Fahim, any progress? For using Cauchy-Schwarz inequality we need product of two sum of square sequences. But since in our left side, there are terms which are not square. Confusing....

In Cauchy-Schwarz LHS has two sum of square sequences, right? And remember that the one greater should be the LHS here.

[zadid xcalibured]

By cauchy schawrtz inequality(£|xi-xj|)^2<n(n-1)/2{£(xi-xj)^2}all we need to prove is that n(n-1)/2<2/3(n^2-1).this is true because n^2+3n-4>0.here £ means sigma.how can this solution be so simple?