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 "2006 IMO Shortlist Problems/A4"

(New page: == Problem == Prove the inequality <cmath> \sum_{i<j} \frac{a_ia_j}{a_i+a_j} \le \frac{n}{2(a_1 + a_2 + \dotsb a_n)} \sum_{i<j} a_i a_j </cmath> for positive real numbers <math>a_1, \dots...)
 
(whoops, submitted it before I was done the first time)
 
Line 8: Line 8:
  
 
Note that
 
Note that
−
<cmath> \sum_{i<j} \frac{a_ia_j}{a_i+a_j} = 1/2 \sum_{i\neq j} \frac{a_ia_j}{a_i + a_j} = 1/2 \sum_{i=1}^n \sum_{j\neq i} \frac{1}{1/a_i + 1/a_j} . </cmath>
+
<cmath> \sum_{i<j} \frac{a_ia_j}{a_i+a_j} = 1/2 \sum_{i\neq j} \frac{a_ia_j}{a_i + a_j} = 1/2 \sum_{j=1}^n \sum_{i\neq j} \frac{1}{1/a_i + 1/a_j} . </cmath>
 
Suppose that <math>1 \le k \neq \ell \le n</math>.  Note that <math>1/(1/a_i + 1/a_j)</math> is an increasing function of both <math>a_i</math> and <math>a_j</math>.  It follows that if <math>a_k \le a_\ell</math>, then
 
Suppose that <math>1 \le k \neq \ell \le n</math>.  Note that <math>1/(1/a_i + 1/a_j)</math> is an increasing function of both <math>a_i</math> and <math>a_j</math>.  It follows that if <math>a_k \le a_\ell</math>, then
 
<cmath> \sum_{j \neq k} \frac{1}{1/a_k + 1/a_j} \le \sum_{j\neq \ell} \frac{1}{a_\ell + a_j}, </cmath>
 
<cmath> \sum_{j \neq k} \frac{1}{1/a_k + 1/a_j} \le \sum_{j\neq \ell} \frac{1}{a_\ell + a_j}, </cmath>
 
i.e., <math>\sum_{j\neq i} \frac{1}{1/a_i + 1/a_j}</math> is an increasing function of <math>j</math>.
 
i.e., <math>\sum_{j\neq i} \frac{1}{1/a_i + 1/a_j}</math> is an increasing function of <math>j</math>.
 +
 +
Since <math>\sum_{i\neq j}(a_j + a_i) = (n-2)a_j + \sum_{i=1}^n a_i</math> is also an increasing function of <math>j</math>, it follows from [[Chebyshev's Inequality]] that
 +
<cmath> \frac{2n-2}{n} \sum_{j=1}^n a_j \cdot \sum_{j=1}^n \sum_{j\neq i} \frac{1}{1/a_i + 1/a_j} \le \sum_{j=1}^n \left[ \sum_{i\neq j} (a_i + a_j) \cdot \sum_{i\neq j} \frac{1}{1/a_i + 1/a_j} \right], </cmath>
 +
or
 +
<cmath> 1/2 \sum_{j=1}^n a_j \cdot \sum_{j=1}^n \sum_{j\neq i} \frac{1}{1/a_i + 1/a_j} \le \frac{n}{4(n-1)} \sum_{j=1}^n \left[ \sum_{i\neq j} (a_i + a_j) \cdot \sum_{i\neq j} \frac{1}{1/a_i + 1/a_j} \right] . </cmath>
 +
Now, for fixed <math>j</math>, both <math>a_i + a_j</math> and <math>1/(1/a_i + 1/a_j)</math> are increasing functions of <math>a_i</math>.  It follows again from Chebyshev's Inequality that
 +
<cmath> \frac{1}{n-1} \sum_{i\neq j} (a_i + a_j) \sum_{i \neq j} \frac{1}{1/a_i + 1/a_j} \le \sum_{i\neq j} \frac{a_i+a_j}{1/a_i + 1/a_j} = \sum_{i\neq j} a_i a_j, </cmath>
 +
or
 +
<cmath> \sum_{i\neq j} (a_i + a_j) \sum_{i \neq j} \frac{1}{1/a_i + 1/a_j} \le (n-1) \sum_{i\neq j} a_ia_j, </cmath>
 +
which in sum becomes
 +
<cmath> \frac{n}{4(n-1)} \sum_{j=1}^n \left[ \sum_{i\neq j}(a_i + a_j) \sum_{i \neq j} \frac{1}{1/a_i + 1/a_j} \right] \le \frac{n}{4} \sum_{j=1}^n \sum_{i \neq j} a_i a_j = \frac{n}{2} \sum_{i<j} a_i a_j .</cmath>
 +
If we denote <math>\sum_{i=1}^n a_i =S</math>, then in summary, we thus have
 +
<cmath> \sum_{i < j} \frac{a_ia_j}{a_i + a_j} = (1/S) \cdot S/2 \cdot \sum_{j=1}^n \sum_{i\neq j} \frac{1}{1/a_i + 1/a_j} \le n/(2S) \cdot \sum_{i<j} a_i a_j, </cmath>
 +
as desired.  <math>\blacksquare</math>
 +
 +
 +
{{alternate solutions}}
 +
 +
== Resources ==
 +
 +
* [[2006 IMO Shortlist Problems]]
 +
* [http://www.mathlinks.ro/Forum/viewtopic.php?p=874975#p874975 Discussion on AoPS/MathLinks]
 +
 +
 +
[[Category:Olympiad Algebra Problems]]

Latest revision as of 12:12, 29 December 2007

Problem

Prove the inequality \[\sum_{i<j} \frac{a_ia_j}{a_i+a_j} \le \frac{n}{2(a_1 + a_2 + \dotsb a_n)} \sum_{i<j} a_i a_j\] for positive real numbers $a_1, \dotsc, a_n$.

Solution

Note that \[\sum_{i<j} \frac{a_ia_j}{a_i+a_j} = 1/2 \sum_{i\neq j} \frac{a_ia_j}{a_i + a_j} = 1/2 \sum_{j=1}^n \sum_{i\neq j} \frac{1}{1/a_i + 1/a_j} .\] Suppose that $1 \le k \neq \ell \le n$. Note that $1/(1/a_i + 1/a_j)$ is an increasing function of both $a_i$ and $a_j$. It follows that if $a_k \le a_\ell$, then \[\sum_{j \neq k} \frac{1}{1/a_k + 1/a_j} \le \sum_{j\neq \ell} \frac{1}{a_\ell + a_j},\] i.e., $\sum_{j\neq i} \frac{1}{1/a_i + 1/a_j}$ is an increasing function of $j$.

Since $\sum_{i\neq j}(a_j + a_i) = (n-2)a_j + \sum_{i=1}^n a_i$ is also an increasing function of $j$, it follows from Chebyshev's Inequality that \[\frac{2n-2}{n} \sum_{j=1}^n a_j \cdot \sum_{j=1}^n \sum_{j\neq i} \frac{1}{1/a_i + 1/a_j} \le \sum_{j=1}^n \left[ \sum_{i\neq j} (a_i + a_j) \cdot \sum_{i\neq j} \frac{1}{1/a_i + 1/a_j} \right],\] or \[1/2 \sum_{j=1}^n a_j \cdot \sum_{j=1}^n \sum_{j\neq i} \frac{1}{1/a_i + 1/a_j} \le \frac{n}{4(n-1)} \sum_{j=1}^n \left[ \sum_{i\neq j} (a_i + a_j) \cdot \sum_{i\neq j} \frac{1}{1/a_i + 1/a_j} \right] .\] Now, for fixed $j$, both $a_i + a_j$ and $1/(1/a_i + 1/a_j)$ are increasing functions of $a_i$. It follows again from Chebyshev's Inequality that \[\frac{1}{n-1} \sum_{i\neq j} (a_i + a_j) \sum_{i \neq j} \frac{1}{1/a_i + 1/a_j} \le \sum_{i\neq j} \frac{a_i+a_j}{1/a_i + 1/a_j} = \sum_{i\neq j} a_i a_j,\] or \[\sum_{i\neq j} (a_i + a_j) \sum_{i \neq j} \frac{1}{1/a_i + 1/a_j} \le (n-1) \sum_{i\neq j} a_ia_j,\] which in sum becomes \[\frac{n}{4(n-1)} \sum_{j=1}^n \left[ \sum_{i\neq j}(a_i + a_j) \sum_{i \neq j} \frac{1}{1/a_i + 1/a_j} \right] \le \frac{n}{4} \sum_{j=1}^n \sum_{i \neq j} a_i a_j = \frac{n}{2} \sum_{i<j} a_i a_j .\] If we denote $\sum_{i=1}^n a_i =S$, then in summary, we thus have \[\sum_{i < j} \frac{a_ia_j}{a_i + a_j} = (1/S) \cdot S/2 \cdot \sum_{j=1}^n \sum_{i\neq j} \frac{1}{1/a_i + 1/a_j} \le n/(2S) \cdot \sum_{i<j} a_i a_j,\] as desired. $\blacksquare$


Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Resources

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2006_IMO_Shortlist_Problems/A4&oldid=21664"