How to arrange $n$ pairs of numbers so that this expression is minimized Consider $n$ pairs of positive integers, $(x_1, y_1), (x_2, y_2), \dots, (x_n, y_n)$. Make a permutation $(a_1, b_1), (a_2, b_2), \dots, (a_n, b_n)$ of these pairs, such that for all $x_i, y_i$, a pair $a_j, b_j$ also exists and such that, 
$$max\left(a_1 + b_1, a_1 + a_2 + b_2, a_1 + a_2 + a_3 + b_3, \dots, \left(\sum_{i=1}^n a_i\right) + b_n\right)$$
is minimized. 
I thought about arranging the pairs such that 
$$a_1 + b_1 \geq a_2 + b_2 \geq \dots \geq a_n + b_n$$
but it can be seen that this does not work by considering the pairs, $(100, 5), (1, 10)$
$$max(100 + 5,  100 + 1 + 10) = 111$$
But, 
$$max(1 + 10,  100 + 5 + 1) = 106$$
which is smaller. 
EDIT: Another solution might be obtained by considering sub-problems of this. If we know the optimum way to permute $i-1$ pairs, can we find the optimum permutation for $i$ pairs?
 A: Hints:


*

*Sorting pairs by $b$'s in a decreasing fashion would give you an optimal solution.

*Optimizing by 
$$\max\left(\color{red}{c}+a_1 + b_1, \color{red}{c}+a_1 + a_2 + b_2, \dots, \color{red}{c}+\left(\sum_{i=1}^n a_i\right) + b_n\right) \tag{$\spadesuit$}$$ gives the same solution set for any constant $\color{red}{c} \in \mathbb{R}$. 

*The intervals, i.e. a connected subsequences, e.g. $$(a_k,b_k),(a_{k+1},b_{k+1}),\ldots,(a_l,b_l)$$ are all valid subproblems – an additive constant (i.e. the initial $a_1+a_2+\ldots+a_{k-1}$) does not change which index generates the highest sum (that is, set $\color{red}{c} = a_1+a_2+\ldots a_{k-1}$).

*A transformation (permutation) of some interval that does not increase the local maximum also does not increase the global maximum.

*Because $a$'s are cumulative, index $m$ being the highest (with respect to $\spadesuit$) in some interval $[k,l]$ implies $$b_i < b_m \quad\text{ for all } i \text{ such that }m < i \leq l.$$

*If index $m$ is the highest (with respect to $\spadesuit$) in $[k,l]$ and $b_m$ is the largest of $b$'s in $[k,l]$ then you can swap $k$ and $m$ without increasing the maximum.

*Start with any optimal solution and prove that you can use the two previous bullets to sort it decreasing by $b$'s (hence proving that such a solution is also optimal).


I hope this helps $\ddot\smile$
