How to prove this inequality involving the minimum of two chosen numbers Let $a_1, b_1, a_2, b_2, \dots , a_n, b_n$ be nonnegative real numbers. Prove that
$$\sum_{i, j = 1}^{n} \min\{a_ia_j, b_ib_j\} \le \sum_{i, j = 1}^{n} \min\{a_ib_j, a_jb_i\}.$$
How do I prove this inequality. I have studied only basic inequalities, namely AM-GM, CS inequality and Tchebycheff's inequality. How do I incorporate that condition of minimum of the two chosen numbers and prove the inequality using the above ones
?
 A: It's USA 2000. The following solution is not mine.
Since if $\min\{a_i,b_i\}=0$ then $\min\{a_ia_j,b_ib_j\}=\min\{a_ib_j,a_jb_i\}=0,$ 
we can assume that $a_i>0$ and $b_i>0$.
Lemma 1.
Let $r_i\geq0$ and $x_i$ be real numbers. Prove that:
$$\sum_{i,j=1}^n\min\{r_i,r_j\}x_ix_j\geq0.$$
Proof.
Since $\min\{r_i,r_j\}=\min\{r_j,r_i\},$ we can assume that $0=r_0\leq r_1\leq r_2\leq...\leq r_n$ and we obtain:
$$\sum_{i,j=1}^n\min\{r_i,r_j\}x_ix_j=\sum_{i=1}^nr_ix_i^2+2\sum_{1\leq i<j\leq n}r_ix_ix_j=\sum_{i=1}^n\left(r_i-r_{i-1}\right)\left(\sum_{j=i}^nx_j\right)^2\geq0.$$
Lemma 2. 
Let $a_i>0$, $b_i>0$, $r_i=\frac{\max\{a_i,b_i\}}{\min\{a_i,b_i\}}-1$ and $x_i=sign(a_i-b_i)\min\{a_i,b_i\}.$ Prove that:
$$\min\{a_ib_j,a_jb_i\}-\min\{a_ia_j,b_ib_j\}=\min\{r_i,r_j\}x_ix_j.$$
Proof.
Since replacing $a_i$ with $b_i$ gives replacing signs of the both sides, we can assume that $a_i\geq b_i$.
Similarly, we can assume that $a_j\geq b_j$ and we obtain:
$$\min\{r_i,r_j\}x_ix_j=\min\left\{\frac{a_i}{b_i}-1,\frac{a_j}{b_j}-1\right\}b_ib_j=$$
$$=\min\{a_ib_j-b_ib_j,a_jb_i-b_ib_j\}=\min\{a_ib_j,a_jb_i\}-b_ib_j=$$
$$=\min\{a_ib_j,a_jb_i\}-\min\{a_ia_j,b_ib_j\}.$$
Now, by applying of these lemmas we obtain:
$$\sum_{i,j=1}^n\min\{a_ib_j,a_jb_i\}-\sum_{i,j=1}^n\min\{a_ia_j,b_ib_j\}=$$
$$=\sum_{i,j=1}^n\left(\min\{a_ib_j,a_jb_i\}-\min\{a_ia_j,b_ib_j\}\right)=\sum_{i,j=1}^n\min\{r_i,r_j\}x_ix_j\geq0$$ and we are done!
For $n=4$ we obtain:
$$(r_4-r_3)x_4^2+(r_3-r_2)(x_3+x_4)^2+(r_2-r_1)(x_2+x_3+x_4)^2+(r_1-r_0)(x_1+x_2+x_3+x_4)^2=$$
$$=r_1x_1^2+(r_2-r_1+r_1)x_2^2+(r_3-r_2+r_2-r_1+r_1)x_3^2+(r_4-r_3+r_3-r_2+r_2-r_1+r_1)x_4^2+$$
$$+2r_1x_1x_2+2r_1x_1x_3+2r_1x_1x_4+2(r_2-r_1+r_1)x_2x_3+$$
$$+2(r_2-r_1+r_1)x_2x_4+2(r_3-r_2+r_2-r_1+r_1)x_3x_4=$$
$$=r_1x_1^2+r_2x_2^2+x_3r_3^2+r_4x_4^2+2r_1x_1x_2+2r_1x_1x_3+2r_1x_1x_4+$$
$$+2r_2x_2x_3+2r_2x_2x_4+2r_3x_3x_4.$$
