Vtyjkyuk

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 mina_ia_j, b_ib_j le sum_i, j = 1^n mina_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
?

It's USA 2000. The following solution is not mine.

Since if $mina_i,b_i=0$ then $mina_ia_j,b_ib_j=mina_ib_j,a_jb_i=0,$

we can assume that $a_i>0$ and $b_i>0$.

Lemma 1.

Let $r_igeq0$ and $x_i$ be real numbers. Prove that:
$$sum_i,j=1^nminr_i,r_jx_ix_jgeq0.$$
Proof.

Since $minr_i,r_j=minr_j,r_i,$ we can assume that $0=r_0leq r_1leq r_2leq...leq r_n$ and we obtain:
$$sum_i,j=1^nminr_i,r_jx_ix_j=sum_i=1^nr_ix_i^2+2sum_1leq i<jleq nr_ix_ix_j=sum_i=1^nleft(r_i-r_i-1right)left(sum_j=i^nx_jright)^2geq0.$$
Lemma 2.

Let $a_i>0$, $b_i>0$, $r_i=fracmaxa_i,b_imina_i,b_i-1$ and $x_i=sign(a_i-b_i)mina_i,b_i.$ Prove that:
$$mina_ib_j,a_jb_i-mina_ia_j,b_ib_j=minr_i,r_jx_ix_j.$$
Proof.

Since replacing $a_i$ with $b_i$ gives replacing signs of the both sides, we can assume that $a_igeq b_i$.

Similarly, we can assume that $a_jgeq b_j$ and we obtain:
$$minr_i,r_jx_ix_j=minleftfraca_ib_i-1,fraca_jb_j-1rightb_ib_j=$$
$$=mina_ib_j-b_ib_j,a_jb_i-b_ib_j=mina_ib_j,a_jb_i-b_ib_j=$$
$$=mina_ib_j,a_jb_i-mina_ia_j,b_ib_j.$$
Now, by applying of these lemmas we obtain:
$$sum_i,j=1^nmina_ib_j,a_jb_i-sum_i,j=1^nmina_ia_j,b_ib_j=$$
$$=sum_i,j=1^nleft(mina_ib_j,a_jb_i-mina_ia_j,b_ib_jright)=sum_i,j=1^nminr_i,r_jx_ix_jgeq0$$ 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.$$