IMO 2006 Shortlisted Problems

Let $S={\sum }_i{a}_i$. Denote by $L$ and $R$ the expressions on the left and right hand side of the proposed inequality. We transform $L$ and $R$ using the identity $$\sum _{i<j}\left(a_i+a_j\right)=(n-1)\sum _i{a}_i.\text{\hspace{1em}(1)}$$ And thus: $$L=\sum _{i<j}\frac{a_i{a}_j}{a_i+a_j}=\sum _{i<j}\frac{1}{4}\left(a_i+a_j-\frac{{\left(a_i-a_j\right)}^2}{a_i+a_j}\right)=\frac{n-1}{4}\cdot S-\frac{1}{4}\sum _{i<j}\frac{{\left(a_i-a_j\right)}^2}{a_i+a_j}.\text{\hspace{1em}(2)}$$ To represent $R$ we express the sum ${\sum }_{i<j}{a}_i{a}_j$ in two ways; in the second transformation identity (1) will be applied to the squares of the numbers $a_i$ : $$\begin{array}{c}\sum _{i<j}{a}_i{a}_j=\frac{1}{2}\left(S^2-\sum _i{a}_i^2\right);\\ \sum _{i<j}{a}_i{a}_j=\frac{1}{2}\sum _{i<j}\left(a_i^2+a_j^2-{\left(a_i-a_j\right)}^2\right)=\frac{n-1}{2}\cdot \sum _i{a}_i^2-\frac{1}{2}\sum _{i<j}{\left(a_i-a_j\right)}^2.\end{array}$$ Multiplying the first of these equalities by $n-1$ and adding the second one we obtain $$n\sum _{i<j}{a}_i{a}_j=\frac{n-1}{2}\cdot S^2-\frac{1}{2}\sum _{i<j}{\left(a_i-a_j\right)}^2.$$ Hence $$R=\frac{n}{2S}\sum _{i<j}{a}_i{a}_j=\frac{n-1}{4}\cdot S-\frac{1}{4}\sum _{i<j}\frac{{\left(a_i-a_j\right)}^2}{S}.\text{\hspace{1em}(3)}$$ Now compare (2) and (3). Since $S\ge a_i+a_j$ for any $i<j$, the claim $L\ge R$ results.

---

Alternative solution.

Let $S=a_1+a_2+\cdots +a_n$. For any $i\ne j$, $$4\frac{a_i{a}_j}{a_i+a_j}=a_i+a_j-\frac{{\left(a_i-a_j\right)}^2}{a_i+a_j}\le a_i+a_j-\frac{{\left(a_i-a_j\right)}^2}{a_1+a_2+\cdots +a_n}=\frac{{\sum }_{k\ne i}{a}_i{a}_k+{\sum }_{k\ne j}{a}_j{a}_k+2a_i{a}_j}{S}.$$ The statement is obtained by summing up these inequalities for all pairs $i,j$ : $$\begin{array}{c}\sum _{i<j}\frac{a_i{a}_j}{a_i+a_j}=\frac{1}{2}\sum _i\sum _{j\ne i}\frac{a_i{a}_j}{a_i+a_j}\le \frac{1}{8S}\sum _i\sum _{j\ne i}\left(\sum _{k\ne i}{a}_i{a}_k+\sum _{k\ne j}{a}_j{a}_k+2a_i{a}_j\right)\\ =\frac{1}{8S}\left(\sum _k\sum _{i\ne k}\sum _{j\ne i}{a}_i{a}_k+\sum _k\sum _{j\ne k}\sum _{i\ne j}{a}_j{a}_k+\sum _i\sum _{j\ne i}2a_i{a}_j\right)\\ =\frac{1}{8S}\left(\sum _k\sum _{i\ne k}(n-1)a_i{a}_k+\sum _k\sum _{j\ne k}(n-1)a_j{a}_k+\sum _i\sum _{j\ne i}2a_i{a}_j\right)\\ =\frac{n}{4S}\sum _i\sum _{j\ne i}{a}_i{a}_j=\frac{n}{2S}\sum _{i<j}{a}_i{a}_j.\end{array}$$