There are $n$ positive numbers (not necessarily distinct). In every step, we can select two numbers and replace each of it with the sum of the two numbers. Prove that in any amount of steps, selecting the two least number in every step minimizes the sum of the $n$ numbers.
When the $n$ numbers are different. We assume that they are $x_1,x_2,..,x_n$. We will also assume that at every step two of of $x_i$ has changed its value so there's no need to define other variables. We can characterize every step by only using the indices, so let step $\{a,b\}$ denote changing each of $x_a$ and $x_b$ to $x_a+a_b$. We also used an arrow ($\rightarrow$) to indicate the order of the steps. Let any arbitrary $k$ steps be $\{i_1,j_1\} \rightarrow \{i_2,j_2\} \rightarrow ... \rightarrow \{i_k,j_k\}$. We can finish the problem by showing that by only changing the first step to select the two least number, will result to smaller than or equal sum. I think there will be induction involved here. Any idea?
