2006 IMO Shortlist Problems/A4

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