Leetcode proof of 2160. Minimum Sum of Four Digit Number After Splitting Digits I was trying to study why the solution of Minimum Sum of Four Digit Number After Splitting Digits, which is listed under the greedy algorithm.
The problem is essentially taking a number of 4 digits $$x_3 x_2 x_1 x_0 = \sum_{j=0}^3 x_j 10^j$$
Divide the digits into two subsets, so effectively generating two new numbers adding them up and obtaing the minimum sum.
The way I formalized the problem is through the following model
$$
\min_{0 \leq k \leq 3, \sigma \in P_4} \left\{\sum_{j=0}^{k} x_{\sigma(j)} 10^j + \sum_{j=0}^{2-k} x_{\sigma(j+k+1)} 10^j \right\}
$$
Here $k + 1$ is supposed the model the number of digits given to the first number and $P_4$ is the set of all possible permutations.
The solution given at the end is essentially taking the permutation the sorts the digits and use the following formula:
$$
\left( x_{\sigma(3)} + x_{\sigma(2)} \right)10 + \left(x_{\sigma(1)} + x_{\sigma(0)} \right)
$$
Can anyone explain why is the solution the right one? I've tried to prove it in several ways but I can't manage.
 A: Lemma
If $\alpha$ and $\beta$ are digits (integers) such that $ 0 \leq \alpha \leq \beta \leq 9 $ and $p$ and $q$ are non-negative integers such that $p<q$, then:
$$ \beta 10^p + \alpha 10^q \leq \alpha 10^p + \beta 10^q $$
Proof of lemma
Let $ \gamma = \beta - \alpha $
Note: $\gamma\geq0$
We have:
$p<q$
$\implies 10^p < 10^q$
$\implies \gamma 10^p \leq \gamma 10^q$ (because $\gamma$ can be $0$)
$\implies \gamma 10^p + \alpha 10^p + \alpha 10^q \leq \gamma 10^q + \alpha 10^p + \alpha 10^q $
$\implies (\gamma + \alpha) 10^p + \alpha 10^q \leq (\gamma + \alpha) 10^q + \alpha 10^p $
$\implies \beta 10^p + \alpha 10^q \leq \beta 10^q + \alpha 10^p $ as required
Solution to the original problem
The lemma can be summarised as "assign lower indices to larger digits".
Suppose $a,b,c,d$ are our digits. Without loss of generality, we have $ 0 \leq a \leq b \leq c \leq d \leq 9 $.
Our goal is to assign the indices $A,B,C,D\in\{0,1,2,3\}$ such that no three of these are the same (we only have two available 'digit slots' for each order of magnitude, since in the end we are to return two numbers), in order to minimise the sum $S(A,B,C,D)=a10^A+b10^B+c10^C+d10^D$.
By the above lemma, at least one of the solutions must have $A \geq B \geq C \geq D$. (This part can be proved by contradiction.)
Finally:
Suppose $S(A',B',C',D')$ is one solution.

*

*A solution must have $D=0$, because $S(A',B',C',0) \leq S(A',B',C',D')$.

*A solution must have $C=0$, because $S(A',B',0,0) \leq S(A',B',C',0)$.

*A solution must have $B=1$, because $S(A',1,0,0) \leq S(A',B',1,0)$. $B=0$ is not allowed for a solution with $D=C=0$, and by this reasoning $B'\neq0$.

*A solution must have $A=1$, because $S(1,1,0,0) \leq S(A',1,1,0)$. $A=0$ is not allowed for a solution with $D=C=0$, and by this reasoning $A'\neq0$.

So $S(1,1,0,0)=10a+10b+c+d$ is a solution.
