Rearrange given numbers to minimize the sum of absolute values of pairwise sums Let $t_1,t_2,\cdots,t_n$ be $n$ real numbers with the following property:
$$\sum_{i=1}^{n}t_i=0$$
I want to find a strategy to achieve the minimum of
$$|t_{i_1}+t_{i_2}|+|t_{i_3}+t_{i_4}|+\cdots+|t_{i_{n-1}}+t_{i_n}|$$
I guess the best strategy is: 
Sort $t_1,t_2,\cdots,t_n$: without loss of generality, assume that $t_1\geq t_2\geq\cdots\geq t_n$. Then, the best choices are $(t_1,t_n)$, $(t_2,t_{n-1})$, $(t_3,t_{n-2})$ and .... . However. I cannot prove the optimality of this strategy.
 A: Assume that your method minimizes $S_n$ and that WLOG there are a greater number of positive $T_i$ than negative $T_i$.  The paragraphs above prove that these pairs are in proper order and minimize $T$.  We are now left to prove that the remaining pairs are properly ordered.
Consider the sum of 2 pairs $S_4=|t_{i_1}+t_{i_2}|+|t_{i_3}+t_{i_4}|$.  Assume WLOG that $t_{i_1}>t_{i_3}>0$ and $t_{i_2},t_{i_4}<0$.  I claim that $S_4$ is minimized when $|t_{i_2}|>|t_{i_4}|$.
Proof: let $u_2=-t_{i_2}$ and $u_4=-t_{i_4}$.  Now $S_4=|t_{i_1}-u_{i_2}|+|t_{i_3}-u_{i_4}|$.  Imagine each $t$ and $u$ as a point on the x-axis.   $|t_{i_1}-u_{i_2}|$ represents the length of string required to connect the two points $t_{i_1}$ and $u_{i_2}$... and $|t_{i_1}-u_{i_2}|+|t_{i_3}-u_{i_4}|$ represents the total length of string required to connect $t_{i_1}$ to $u_{i_2}$ and $t_{i_3}$ to $u_{i_4}$.  The images on THIS PAGE (firstly, I would post the pics but I can't cuz I just joined this site and don't have 10 reputation yet lol.  Secondly, I apologize for naming the points $t_2$ and $t_4$, they should be named $u_2$ and $u_4$) showcase all 12 possibilities with $t_{i_1}>t_{i_3}$.  These images prove that the total length of the string required to connect $t_{i_1}$ to $u_{i_2}$ and $t_{i_3}$ to $u_{i_4}$ is minimized for every configuration when $|t_{i_2}|>|t_{i_4}|$.  I could show this algebraically but it's so much prettier when shown Geometrically.
This proves that for two pairs, their sum is minimized when the two extremes are paired.  If we apply this reasoning to every possible pair of pairs, we arrive at the conclusion that your method is indeed the optimal one for minimizing $T_n$.
