Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2003 IMO Problems/Problem 5"
(→‎Solution)
Line 9: Line 9:
 
==Solution==
 
==Solution==
 
{{solution}}
 
{{solution}}
−
We first make use of symmetry to rewrite the inequality as
+
\[
−
<cmath>\left(\sum_{1\le i<j\le n}|x_i-x_j|\right)^2\le\frac{n^2-1}3\left(\sum_{1\le i<j\le n}|x_i-x_j|^2\right)</cmath>.
+
\text{We first make use of symmetry to rewrite the inequality as}
−
WLOG that <math>x_1\le x_2\le\dots\le x_n</math> and let <math>x_{i-1}-x_i=a_i</math>. The inequality is equivalent to
+
\]
−
<cmath>\left(\sum_{1\le i<j\le n}\left(a_i+\dots+a_{j-1}\right) \right)^2\le\frac{n^2-1}3\left(\sum_{1\le i<j\le n}\left(a_i+\dots+a_{j-1}\right)^2\right)</cmath>for all <math>a_1,\dots,a_{n-1}</math>.
+
\[
−
But this can be rewritten 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="">\]
−
<cmath>\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)</cmath>
+
\[
−
By Cauchy-Schwarz:
+
\text{WLOG that } x_1\le x_2\le\dots\le x_n \text{ and let } x_{i-1}-x_i=a_i.
−
\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
+
\text{The inequality is equivalent to}
−
\end{align*}
+
\]
 +
\[
 +
\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)&amp;\ge\left(\sum_{l=1}^{n-1}\sum_{j-i=l}l\left(a_i+\dots+a_j\right)\right)^2\\ &amp;=\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 } <math>l\times(n-l)</math> \text{ matrix:}
 +
\[
 +
\left( \begin{array}{cccc}
 +
a_1 &amp; a_2 &amp; \dots &amp; a_l \\
 +
a_2 &amp; a_3 &amp; \dots &amp; a_{l+1} \\
 +
\vdots &amp; \vdots &amp; \ddots &amp; \vdots\\
 +
a_{n-l} &amp; a_{n-l+1} &amp; \dots &amp; 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&amp;=\left(\sum_{l=1}^{n-1}\frac n2\sum_{j-i=l}\left(a_i+\dots+a_j\right)\right)^2\\ &amp;=\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>
  
−
We claim that
 
−
<cmath>\sum_{j-i=l}(a_i+\dots+a_j)=\sum_{j-i=(n-l)}(a_i+\dots+a_j)</cmath>. Indeed, we may consider the <math>l\times(n-l)</math> 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)\]
 
−
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.
 
−
 
−
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*}
 
−
 
−
We may also check that
 
−
<cmath>\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}</cmath>. Thus we have proven that
 
−
<cmath>\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</cmath>
 
−
Dividing <math>\frac{n^2}4</math> yields
 
−
<cmath>\frac{n^2-1}{3}\left(\sum_{l=1}^{n-1}\sum_{j-i=l}\left(a_i+\dots+a_{j}\right)^2\right)\ge\left(\sum_{l=1}^{n-1}\sum_{j-i=l}\left(a_i+\dots+a_j\right)\right)^2</cmath>as desired.
 
−
 
−
Furthermore, from Cauchy's equality condition, equality holds if and only if <math>a_1=a_2=\dots=a_{n-1}</math> - that is, when the <math>x_i</math> form an arithmetic sequence.
 
 
==See Also==
 
==See Also==
  
 
{{IMO box|year=2003|num-b=4|num-a=6}}
 
{{IMO box|year=2003|num-b=4|num-a=6}}

Revision as of 14:29, 3 December 2023

Problem

Let $n$ be a positive integer and let $x_1 \le x_2 \le \cdots \le x_n$ be real numbers. Prove that

\[\left( \sum_{i=1}^{n}\sum_{j=i}^{n} |x_i-x_j|\right)^2 \le \frac{2(n^2-1)}{3}\sum_{i=1}^{n}\sum_{j=i}^{n}(x_i-x_j)^2\]

with equality if and only if $x_1, x_2, ..., x_n$ 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 } $l\times(n-l)$ \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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2003_IMO_Problems/Problem_5&oldid=206430"