## 2003 IMO Problem 5

Discussion on International Mathematical Olympiad (IMO)
Posts: 217
Joined: Thu Oct 27, 2011 11:04 am
Location: mymensingh

### Re: 2003 IMO Problem 5

is something wrong with my solution?

Corei13
Posts: 153
Joined: Tue Dec 07, 2010 9:10 pm
Location: Chittagong

### Re: 2003 IMO Problem 5

$\left( \sum^n_{i, j = 1} |x_i - x_j | \right)^2 \leq \frac{2 (n^2 - 1)}{3} \sum^n_{i, j = 1} (x_i - x_j)^2$
$\Longleftrightarrow \left( \sum_{1 \leq i < j \leq n} |x_i - x_j | \right)^2 \leq \frac{(n^2 - 1)}{3} \sum_{1 \leq i < j \leq n} (x_i - x_j)^2$
$\Longleftrightarrow \left( \sum_{i < j} \sum^{j - 1}_{k = i} a_k \right)^2 \leq \frac{n^2 - 1}{3} \sum_{i < j} \left( \sum^{j - 1}_{k = i} a_k \right)^2$
Now, by Cachy-Schwarz
$\text{\frac{n^2 - 1}{3} \left( \sum_{i < j} \left( \sum^{j - 1}_{k = i} a_k \right)^2 \right)} \left( \sum_{i < j} (j - i)^2 \right) \geq \frac{n^2 - 1}{3} \left( \sum_{i < j} \left( (j - i) \sum_{k = i}^{j - 1} a_k \right) \right)^2$
so, we needit's enough to prove,

$\frac{n^2 - 1}{3} \left( \sum_{i < j} \left( (j - i) \sum_{k = i}^{j - 1} a_k \right) \right)^2 \geq \left( \sum_{i < j} (j - i)^2 \right) \left( \sum_{i < j} \sum^{j - 1}_{k = i} a_k \right)^2$
Belive it or not, there's no more inequality!

Now.

$\sum_{i < j} \sum^{j - 1}_{k = i} a_k$

$= \sum_k \sum_{i \leq k} \sum_{j > k} a_k$

$= \sum_k \left( \sum_{1 \leq i \leq k} 1 \right) \left( \sum_{n \geq j > k} 1 \right) a_k$

$= \sum_k k (n - k) a_k$

And,

$\sum_{i < j} \left( (j - i) \sum_{k = i}^{j - 1} a_k \right)$

$= \sum_k \sum_{i \leq k} \sum_{j > k} (j - i) a_k$

$= \sum_k \left( \sum_{i \leq k} \sum_{n \geq j > k} j \right) a_k - \sum_k \left( \sum_{n \geq j > k} \sum_{i \leq k} i \right) a_k$

$= \sum_k \left( \sum_{i \leq k} \left( (k + 1) + \cdots + n \right) \right) a_k - \sum_k \left( \sum_{n \geq j > k} \left( 1 + 2 + \cdots + k \right) \right) a_k$

$= \sum_k \left( \sum_{i \leq k} \frac{n (n + 1) - k (k + 1)}{2} \right) a_k - \sum_k \left( \sum_{n \geq j > k} \frac{k (k + 1)}{2} \right) a_k$

$= \sum_k \frac{k (n + k + 1) (n - k)}{2} a_k - \sum_k \frac{(n - k) k (k + 1)}{2} a_k$

$= \sum_k \frac{n k (n - k)}{2}$

$= \frac{n}{2} \left( \sum_{i < j} \sum^{j - 1}_{k = i} a_k \right)$

So, it remains to prove:
$\frac{n^2 (n^2 - 1)}{12} \geq \sum_{i < j} (j - i)^2$
Indeed,

$\sum_{i < j} (i - j)^2$

$= \sum_{1 \leq i < j \leq n} (i - j)^2$

$= \sum_{i = 1}^{n - 1} \sum_{j = i}^n (i - j)^2$

$= \sum_{i = 1}^{n - 1} \sum_{j - i = 1}^{n - i} (j - i)^2$

$= \sum_{n - i = 1}^{n - 1} \frac{(n - i + 1) (n - i) (2 (n - i) + 1)}{6}$

$= \sum_{k = 1}^{n - 1} \frac{k (k + 1) (2 k + 1)}{6}$

$= \sum_{k = 1}^{n - 1} ( \frac{k^3}{3} + \frac{k^2}{2} + \frac{k}{6})$

$= \frac{1}{3} \frac{n^2 (n - 1)^2}{4} + \frac{1}{2} \frac{n (n - 1) (2 n - 1)}{6} + \frac{1}{6} \frac{n (n - 1)}{2}$

$= \frac{n^4 - 2 n^3 + n^2 + 2 n^3 - 3 n^2 + n + n^2 - n}{12}$

$= \frac{n^4 - n^2}{12}$

$= \frac{n^2 (n^2 - 1)}{12} !$
ধনঞ্জয় বিশ্বাস