2003 IMO Problem 5

Discussion on International Mathematical Olympiad (IMO)
sourav das
Posts: 461
Joined: Wed Dec 15, 2010 10:05 am
Location: Dhaka
Contact:

2003 IMO Problem 5

Unread post by sourav das » Thu Oct 27, 2011 10:20 pm

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 :D
You spin my head right round right round,
When you go down, when you go down down......
(-$from$ "$THE$ $UGLY$ $TRUTH$" )

sourav das
Posts: 461
Joined: Wed Dec 15, 2010 10:05 am
Location: Dhaka
Contact:

Re: 2003 IMO Problem 5

Unread post by sourav das » Fri Oct 28, 2011 12:35 am

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.
You spin my head right round right round,
When you go down, when you go down down......
(-$from$ "$THE$ $UGLY$ $TRUTH$" )

User avatar
*Mahi*
Posts: 1175
Joined: Wed Dec 29, 2010 12:46 pm
Location: 23.786228,90.354974
Contact:

Re: 2003 IMO Problem 5

Unread post by *Mahi* » Fri Oct 28, 2011 10:21 am

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!
Please read Forum Guide and Rules before you post.

Use $L^AT_EX$, It makes our work a lot easier!

Nur Muhammad Shafiullah | Mahi

sourav das
Posts: 461
Joined: Wed Dec 15, 2010 10:05 am
Location: Dhaka
Contact:

Re: 2003 IMO Problem 5

Unread post by sourav das » Fri Oct 28, 2011 10:39 am

*Mahi* wrote: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 :) )
You spin my head right round right round,
When you go down, when you go down down......
(-$from$ "$THE$ $UGLY$ $TRUTH$" )

User avatar
FahimFerdous
Posts: 176
Joined: Thu Dec 09, 2010 12:50 am
Location: Mymensingh, Bangladesh

Re: 2003 IMO Problem 5

Unread post by FahimFerdous » Fri Oct 28, 2011 11:30 am

I completely agree with Sourav. So Mahi, please tell how you started thinking about the first step.
Your hot head might dominate your good heart!

sourav das
Posts: 461
Joined: Wed Dec 15, 2010 10:05 am
Location: Dhaka
Contact:

Re: 2003 IMO Problem 5

Unread post by sourav das » Fri Oct 28, 2011 12:49 pm

Is it because of Cauchy-Schwarz equality condition has similarity with the difference between two elements of an arithmetic progression?
You spin my head right round right round,
When you go down, when you go down down......
(-$from$ "$THE$ $UGLY$ $TRUTH$" )

User avatar
*Mahi*
Posts: 1175
Joined: Wed Dec 29, 2010 12:46 pm
Location: 23.786228,90.354974
Contact:

Re: 2003 IMO Problem 5

Unread post by *Mahi* » Fri Oct 28, 2011 1:50 pm

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!
Last edited by *Mahi* on Fri Oct 28, 2011 9:49 pm, edited 1 time in total.
Please read Forum Guide and Rules before you post.

Use $L^AT_EX$, It makes our work a lot easier!

Nur Muhammad Shafiullah | Mahi

sourav das
Posts: 461
Joined: Wed Dec 15, 2010 10:05 am
Location: Dhaka
Contact:

Re: 2003 IMO Problem 5

Unread post by sourav das » Fri Oct 28, 2011 8:50 pm

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....
You spin my head right round right round,
When you go down, when you go down down......
(-$from$ "$THE$ $UGLY$ $TRUTH$" )

User avatar
*Mahi*
Posts: 1175
Joined: Wed Dec 29, 2010 12:46 pm
Location: 23.786228,90.354974
Contact:

Re: 2003 IMO Problem 5

Unread post by *Mahi* » Fri Oct 28, 2011 9:51 pm

sourav das wrote: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.
Please read Forum Guide and Rules before you post.

Use $L^AT_EX$, It makes our work a lot easier!

Nur Muhammad Shafiullah | Mahi

User avatar
zadid xcalibured
Posts: 217
Joined: Thu Oct 27, 2011 11:04 am
Location: mymensingh

Re: 2003 IMO Problem 5

Unread post by zadid xcalibured » Fri Oct 28, 2011 10:05 pm

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?

Post Reply