# Greedy algorithms: Minimum sum number pairing

Given $n$ real numbers (where $n$ is even) find a pairing which minimizes the maximum sum of a pair.

I think the optimal pairing is obtained by sorting the original set, pairing the first element with the last one, and so on. But I get stuck trying to prove it.

I tried use the "difference reduction method", examining differences between an optimal answer and the "greedy" answer, and trying to get the greedy from the optimal without losing optimality, but I didn't reach anything. Any idea?

Suppose that numbers are $x_1, \ldots x_{2n}$, and let us rename them as $a_1, \ldots a_n, b_1, \ldots, b_n$, where $a_i \geq b_j$ for any $i, j$, $a_1 \geq a_2 \geq \ldots \geq a_n$, and $b_1 \leq b_2 \leq \ldots \leq b_n$. In this notation, the suggested optimum solution is $(a_1, b_1), \ldots (a_n, b_n)$.

Given some arbitrary pairing, let us show we can reduce it to the right pairing without increasing the maximum sum of a pair. This shows that the expected correct solution is at least as good as any other. Equality might hold, eg. if all the values are the same, then any pairing is the joint best.

First suppose that there is some pair $(a_u, a_v)$. Then since there are an equal number of $a$'s and $b$'s, there must also be some pair $(b_s, b_t)$. Clearly $a_u + a_v \geq b_s + b_t$, furthermore $a_u + a_v \geq a_u + b_s$ and similarly $a_u + a_v \geq a_v + b_t$. So if we replace the pairs $(a_u, a_v), (b_s, b_t)$ by $(a_u, b_s), (a_v, b_t)$, we have reduced the maximum sum of a pair, or at worst kept it the same.

So now assume that our pairing is of the form $(a_{i_1}, b_{i_1}), \ldots (a_{i_n}, b_{i_n})$, but that it's not $(a_1, b_1), \ldots (a_n, b_n)$. There must be at least one pair of pairs, $(a_j, b_k)$ and $(a_l, b_m)$, where $j < l$ but $k > m$. (Otherwise, the $b$'s are in the same order as the $a$'s, which means it's the suggested solution.)

This means that $a_j \leq a_l$ and $b_k \leq b_m$. So $a_l + b_m \geq a_j + b_k$, also $a_l + b_m \geq a_j + b_m$, and similarly $a_l + b_m \geq a_l + b_k$. So $(a_l, b_m)$ must be the bigger of $(a_j, b_k), (a_l, b_m)$, and replacing those two pairs with $(a_l, b_k), (a_j, b_m)$ can only reduce the maximum (or keep it the same).

This shows that whatever pairing we start out with, we can swap pairs until we reach the suggested solution, without making the maximum sum any bigger. So the suggested solution must be the best.

I believe you could collapse the two steps into a single argument since both are very similar and rely on showing that two pairs can be 'flipped' without making the maximum sum any bigger. However I find it easier to imagine in two stages.