# Proof of sorting algorithm.

• #### Proof

Suppose we have an optimal solution:
`S_maximum = min(a_smallest, a_j) + S_other` where `a_smallest` is the smallest number in the integer set and `a_j` is greater or equal to `a_smallest`.

Let us proof the following statement.
If there is a number (or numbers) `a_between_a_smallest_and_a_j` between `a_smallest` and `a_j` then it must satisfy to the condition: the second number paired with `a_between_a_smallest_and_a_j` can be only with the same value as `a_between_a_smallest_and_a_j`, i.e. there are two variants for optimal solution:

• `S_maximum = min(a_smallest, a_j) + S_other`, where `a_j` - next smallest after `a_smallest`
• `S_maximum = min(a_smallest, a_j) + min(a2, a2) + min(a3, a3) + ... + S_other`, where `a_smallest <= a2 <= a3 <= a_j`.

Suppose there is a number `a_i` between: `a_smallest < a_i < a_j` in solution. His paired number is `a_k`. So the optimal sum looks like: `S_maximum = min(a_smallest, a_j) + min(a_i, a_k) + S_other.`
If `a_i < a_k`, then we can get greater sum with `S_maximum = min(a_smallest, a_i) + min(a_k, a_j) + S_other`, because `a_j > a_i` and `a_k > a_i` . Contradiction!
If `a_i > a_k`, then we can greater sum with `S_maximum = min(a_smallest, a_k) + min(a_i, a_j) + S_other`. Contradiction!
So for fixed smallest number `a1` the optimal solution looks like: `min(a1, a2) + other` where `a2` - next smallest after `a1` or `min(a1, aj) + min(a2, a2) + min(a3, a3) + other` where `a1 <= a2 <= a3 <= aj`. Both this variants we can rewrote without decreasing sum into `min(a1, a2) + min(a2, a3) + min(a3, a3) + min(a3, aj) + min(a4, a5)` where `a1<=a2=a2(second)=a3=a3=a3=a3<=aj` - but this is just sorted numbers paired! So `a_smallest` can be only paired with next smallest number. Iterating through `S_other` with this logic we just get solution with sorting idea.
The logic behind this is if we have an optimal solution `S_max = min(a_smallest, a_k) + S_optimal_other` we can replace `a_k` with the next smallest number after `a_smallest` (`a_smallest_2`) and put `a_k` in old `a_smallest_2` position without decreasing sum. Repeating this trick for `S_optimal_other` we get sorted pairs.