How to come up with a greedy solution and prove it? Say we have a function $S(x)$, which gives the sum of the digits in the number $x$. So $S(452)$ would be $4 + 5 + 2 = 11$. Given a number $x$, find two integers $a, b$ such that $0 <= a, b <= x$ and $a + b = x$. Objective is to maximize $S(a) + S(b)$. I came across this question on a programming website and the answer is to greedily choose a number $a$ containing all $9$'s such that it is lesser than $x$, and the other number would be $x - a$. If $x = 452$, then $S(99) + S(353) = 29$ which is the maximum possible. How do I come up with this and prove the same?

Show the following two statements (I guess they would be lemmas):

1. When adding $a+b$ the way you learn in school, if you get no carries, then $S(a+b)=S(a)+S(b)$

2. For each carry you get when adding $a+b$, the sum $S(a)+S(b)$ increases by $9$.




Together they mean that you want to have as many carries as you can. The greedy algorithm you describe gives you a carry into each column (except the 1's column, which is impossible anyways) and therefore gives you the max.