OPT:
a_1 + a_2 + ... + a_n/2 = a_sum
b_1 + b_2 + ... + b_n/2 = b_sum

stuck:
c_1 + c_2 + ... + c_n/2 = c_sum
d_1 + d_2 + ... + d_n/2 = d_sum

WLOG assumptions:
ordered by rating: a_i < a_i+1, b_i < b_i+1, etc.
unique solution
a_sum < b_sum, c_sum < d_sum

assume no such swap can decrease |d_sum - c_sum|
i.e. for all 1<=i, j<=n/2
| d_sum - d_i + c_j - (c_sum - c_j + d_i) | > d_sum - c_sum

so

1. d_sum - d_i + c_j - (c_sum - c_j + d_i) > d_sum - c_sum
OR
2. d_sum - d_i + c_j - (c_sum - c_j + d_i) < c_sum - d_sum

from 1:
A: c_j - d_i > 0 => c_j > d_i
OR
from 2:
B: c_j - d_i < c_sum - d_sum



By definition, d_sum-c_sum > b_sum-a_sum

Note that no such swap can decrease |b_sum - a_sum| either.

So we also get
C: a_j - b_i > 0 => a_j > b_i
OR
D: a_j - b_i < a_sum - b_sum

for all j, i

Let's start to pick relevant p, q

p is the first index that c_p != a_p
q is the first index that d_q != b_q

Case 1
c_p < a_p
and
d_q < b_q

This is not possible. min(c_p, d_q) would have caused an earlier conflict, so one of p or q would not have been the first index.

By symmetry,
Case 4
c_p > a_p
and
d_q > d_q
is also impossible.

Leaving just
Case 2
c_p < a_p
and
d_q > b_q

OR

Case 3
c_p > a_p
and
d_q < b_q

Note that by symmetry, we actually only need to solve one of these 2 cases.

Case 2
subcase AC:
c_p > d_q
a_p > b_q

Then a_p > c_p > d_q > b_q

This is not possible. element b_q must appear somewhere in c, d, but we already said this is the first difference. As the unique minimum of those 4 elements, b_q would have caused an earlier difference. Contradiction!

subcase BD:
a_p - b_q < a_sum - b_sum
c_p - d_q < c_sum - d_sum
With c_p < a_p and d_q > b_q,

c_p - d_q  < a_sum - b_sum < c_sum - d_sum

Recall above that by definition, our stuck solution d_sum - c_sum > b_sum - a_sum. But this is a contradiction with the second part of the above inequality!

subcase AD (and BC by symmetry)
c_p > d_q
a_p - b_q < a_sum - b_sum
With c_p < a_p and d_q > b_q =>

c_p - d_q < a_p - b_q < a_sum-b_sum

Note that c_p - d_q is still positive and less than a_sum - b_sum. So, this means that making the same swap would actually improve OPT. Contradiction! OPT is not optimal.

All cases reached contradiction, meaning that our strategy will reach the correct solution and won't get "stuck" anywhere! QED