a bit of random stuff: Rearrangement Inequality

Theorem:
Let \(x_1 \leq x_2 \leq \ldots \leq x_n \), \( y_1 \leq y_2 \leq \ldots \leq y_n \),  and \(S = x_1y_2 + x_2y_2 + \ldots + x_ny_n\). Then \(S \geq \sum x'y'\) Where \(x'\) and \(y'\) is some permutation of \(x_i\) and \(y_i\).

Proof:
First we prove the case where \(n = 2\):
Since \(x_1 \leq x_2\) and \(y_1 \leq y_2\) we have \(0 \leq (x_2-x_1)(y_2-y_1) = x_2y_2 +x_1y_2 - (x_1y_2+x_2y_1) \) and hence \(x_2y_2 +x_1y_2 \geq x_1y_2+x_2y_1 \).

This means that whenever we see two pairs \(x_1y_2\) and \(x_2y_1\), swapping the \(y_1\) and \(y_2\) will lead to a larger value.

Suppose that there is \(S'\) that is larger than \(S\). Then there is some \(x'_iy'_i\) and \(x'_jy'_j\) in \(S'\) such that either:
1.  \(x'_i \leq x'_j \text{ and } y'_i \geq y'_j\) or
2. \( x'_i \geq x'_j \text{ and } y'_i \leq y'_j\)
Because if there is not such pairs, then every pair is in the form \(x'_i \leq x'_j \) and \(y'_i \leq y'_j\) which by incremental construction will lead to the conclusion that \(S' = S\) which is not the case.
Then we can swap \(y'_i\) and \(y'_j\) and arrive at a larger value than \(S'\), a contradiction. Therefore \(S\) must have been maximal.