Problem: 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_i a_j, b_i b_j\}
  \le \sum_{i, j = 1}^{n} \min\{a_i b_j, a_j b_i\}.  \]

\end{enumerate}

Solution: We present two solutions.

\paragraph{First solution by creating a single min (Vincent Huang and Ravi Boppana).}
Let $b_i = r_i a_i$ for each $i$,
and rewrite the inequality as
\[ \sum_{i,j} a_i a_j \left[
  \min (r_i, r_j) - \min(1, r_i r_j) \right] \ge 0. \]
We now do the key manipulation to convert the double min
into a separate single min.
Let $\eps_i = +1$ if $r_i \ge 1$, and $\eps_i = -1$ otherwise,
and let $s_i = |r_i-1|$.
Then we pass to absolute values:
\begin{align*}
  2\min(r_i,r_j) - 2\min(1,r_i r_j)
  &= |r_i r_j-1| - |r_i-r_j|  - (r_i-1)(r_j-1) \\
  &= |r_i r_j-1| - |r_i-r_j| - \eps_i \eps_j s_i s_j \\
  &= \eps_i \eps_j \min \left( |1-r_i r_j \pm (r_i-r_j)| \right)
  - \eps_i \eps_j s_i s_j \\
  &= \eps_i \eps_j \min \left( s_i(r_j+1), s_j(r_i+1) \right)
  - \eps_i \eps_j s_i s_j \\
  &= (\eps_i s_i)(\eps_j s_j)
  \min \left( \frac{r_j+1}{s_j}-1, \frac{r_i+1}{s_i}-1  \right).
\end{align*}
So let us denote $x_i = a_i \eps_i s_i \in \RR$,
and $t_i = \frac{r_i+1}{s_i}-1 \in \RR_{\ge 0}$.
Thus it suffices to prove that:
\begin{claim*}
  We have
  \[ \sum_{i,j} x_i x_j \min(t_i, t_j) \ge 0 \]
  for arbitrary $x_i \in \RR$, $t_i \in \RR_{\ge 0}$.
\end{claim*}
\begin{proof}
  One can just check this ``by hand''
  by assuming $t_1 \le t_2 \le \dots \le t_n$;
  then the left-hand side becomes
  \[ \sum_i t_i x_i^2 + 2 \sum_{i < j} 2 t_i x_i x_j
    = \sum_i (t_i - t_{i-1}) (x_i + x_{i+1} + \dots + x_n)^2 \ge 0.  \]
  There is also a nice proof using the integral identity
  \[ \min(t_i, t_j) = \int_0^\infty \mathbf1(u \le t_i) \mathbf1(u \le t_j) \; du \]
  where the $\mathbf1$ are indicator functions.
  Indeed,
  \begin{align*}
    \sum_{i,j} x_i x_j \min(t_i, t_j)
    &= \sum_{i,j} x_i x_j \int_0^\infty \mathbf1(u \le t_i) \mathbf1(u \le t_j) \; du \\
    &= \int_0^\infty \sum_i x_i \mathbf1(u \le t_i)
    \sum_j x_j \mathbf1(u \le t_j) \; du \\
    &= \int_0^\infty \left( \sum_i x_i \mathbf1(u \le t_i) \right)^2 \; du \\
    &\ge 0. \qedhere
  \end{align*}
\end{proof}


\paragraph{Second solution by smoothing (Alex Zhai).}
The case $n=1$ is immediate, so we'll proceed by induction on $n \ge 2$.

Again, let $b_i = r_i a_i$ for each $i$, and
write the inequality as
\[ L_n(a_1, \dots, a_n, r_1, \dots, r_n)
  \coloneq \sum_{i,j} a_i a_j \left[
  \min (r_i, r_j) - \min(1, r_i r_j) \right] \ge 0. \]
First note that if $r_1 = r_2$ then
\[ L_n(a_1, a_2, a_3, \dots, r_1, r_1, r_3 \dots)
  = L_{n-1}(a_1+a_2, a_3, \dots, r_1, r_3, \dots) \]
and so our goal is to smooth to a situation
where two of the $r_i$'s are equal,
so that we may apply induction.

On the other hand, $L_n$ is a \emph{piecewise linear} function in $r_1 \ge 0$.
Let us smooth $r_1$ then.
Note that if the minimum is attained at $r_1 = 0$,
we can ignore $a_1$ and reduce to the $(n-1)$-variable case.
On the other hand, the minimum must be achieved at a cusp
which opens upward, which can only happen if $r_i r_j = 1$ for some $j$.
(The $r_i = r_j$ cusps open downward, sadly.)

In this way, whenever some $r_i$ is not equal to the reciprocal
of any other $r_\bullet$, we can smooth it.
This terminates; so we may smooth until we reach a situation for which
\[ \{ r_1, \dots, r_n \} = \{ 1/r_1, \dots, 1/r_n \}. \]
Now, assume WLOG that $r_1 = \max_i r_i$ and $r_2 = \min_i r_i$,
hence $r_1 r_2 = 1$ and $r_1 \ge 1 \ge r_2$.
We isolate the contributions from $a_1$, $a_2$, $r_1$ and $r_2$.
\begin{align*}
  L_n(\dots) &= a_1^2 \left[ r_1 - 1  \right] + a_2^2 \left[ r_2 - r_2^2 \right]
    + 2a_1a_2 \left[ r_2 - 1 \right] \\
  &+ 2a_1 \left[ (a_3r_3+\dots+a_n r_n) - (a_3+\dots+a_n) \right] \\
  &+ 2a_2r_2 \left[ (a_3+\dots+a_n) - (a_3r_3+\dots+a_n r_n) \right] \\
  &+ \sum_{i=3}^n \sum_{j=3}^n a_i a_j \left[
    \min (r_i, r_j) - \min(1, r_i r_j) \right].
\end{align*}
The idea now is to smooth via
\[ (a_1, a_2, r_1, r_2)
  \longrightarrow
  \left( a_1, \frac 1t a_2, \frac 1t r_1, tr_2 \right) \]
where $t \ge 1$ is such that
$\frac 1t r_1 \ge \max(1, r_3, \dots, r_n)$ holds.
(This choice is such that $a_1$ and $a_2 r_2$ are unchanged,
because we don't know the sign of $\sum_{i \ge 3} (1-r_i) a_i$
and so the post-smoothing value is still at least the max.)
Then,
\begin{align*}
  &\phantom{ {} = {} } L_n(a_1, a_2, \dots, r_1, r_2, \dots)
  - L_n\left(a_1, \frac 1t a_2, \dots, \frac1t r_1, tr_2\right) \\
  &= a_1^2 \left( r_1 - \frac 1t r_1 \right)
  + a_2^2 \left( r_2 - \frac 1t r_2 \right)
  + 2a_1a_2 \left( \frac 1t - 1 \right) \\
  &= \left( 1 - \frac 1t \right) \left( r_1 a_1^2 + r_2 a_2^2 - 2a_1a_2 \right)
  \ge 0
\end{align*}
the last line by AM-GM.
Now pick $t = \frac{r_1}{\max(1, r_3, \dots, r_n)}$,
and at last we can induct down.