A while back I asked about the solution of a certain contest problem. While working on it I came to this inequality:
For $x_1<x_2<\cdots<x_n$ and $y_1 < y_2 <\cdots y_n$, prove that
$$ \sum_{\sigma \text{ even}} \sum_{i=1}^n x_iy_{\sigma{(i)}} > \sum_{\sigma \text{ odd}} \sum_{i=1}^n x_i y_{\sigma{(i)}} $$ where the outer sums run over all even/odd permutations $\sigma$ of $\{ 1, \ldots, n \}$.
This is true but the only proof of it that I have is by solving the original contest problem and reversing the steps I used to come to it. Is there a combinatorics/analysis proof of it?
For $n=1$ the inequality becomes $$ x_1 y_1 > 0 $$ about which nothing can be said as $x_1, y_1$ can have arbitrary sign.
If $n=2$ then the difference between left-hand side and right-hand side is $$ (x_1 y_1 + y_2 y_2) - (x_1 y_2 + x_2y_1) = (x_2 - x_1)(y_2 - y_1) > 0 $$ so that the (strict) inequality holds.
And for $n \ge 3$ the expression are in fact equal: $$ \sum_{\sigma \text{ even}} \sum_{i=1}^n x_iy_{\sigma{(i)}} - \sum_{\sigma \text{ odd}} \sum_{i=1}^n x_i y_{\sigma{(i)}} = \sum_{i=1}^n x_i \left( \sum_{\sigma \text{ even}} y_{\sigma{(i)}} - \sum_{\sigma \text{ odd}} y_{\sigma{(i)}} \right) = 0 $$ because for each $k \in\{ 1, \ldots, n \}$, $\sigma{(i)}=k$ for the same number of even and odd permutations.