2003 IMO Problem 5

Discussion on International Mathematical Olympiad (IMO)
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:12 pm

is something wrong with my solution?

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

Re: 2003 IMO Problem 5

Unread post by Corei13 » Sat Oct 29, 2011 12:54 am

\[ \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} !$
ধনঞ্জয় বিশ্বাস

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 » Sat Oct 29, 2011 6:46 am

sorry i found out where my mistake is.

Post Reply