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
Let us proof the following statement.
If there is a number (or numbers)
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
S_maximum = min(a_smallest, a_j) + min(a2, a2) + min(a3, a3) + ... + S_other, where
a_smallest <= a2 <= a3 <= a_j.
We prove by contradiction.
Suppose there is a number
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.
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!
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
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_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.