How to come up with a greedy solution and prove it?

Question

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?

Answer 1

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.

Answer 2

Elaborating on the process in lulu's comment:

Since there are only finitely many choices for $a,b$, an optimum must exist. Consider all pairs $(a,b)$ with $a+b=n$ and $S(a)+S(b)=\max$ and $a\le b$. $a=\overline{a_1a_2\ldots a_d}$ and $b=\overline{b_1b_2\ldots b_d}$ (with $b_1>0$, but possibly $a_1=0$). Among all such $(a,b)$, pick one that maximizes $S(a)$.

Suppose $a_k<9$ for some $k>1$.

• If $b_k=0$, then there must be a (maximal) $j<k$ with $b_j>0$, for otherwise we'd have $b<a$. If we replace $a_k$ with $a_k+1$, $b_j$ with $b_j-1$ and $b_i$ with $9$ for $j<i\le k$, with the numbers $a',b'$ obtained this way, we have $a'+b'=a+b=n$, but $S(a')+S(b')=S(a)+S(b)+9(k-j)$, constradicting maximality of $S(a)+S(b)$.

• If $b_k>0$ we could increase $a_k$ and decrease $b_k$ by one, thereby achieving $a'+b'=a+b=n$, $S(a')+S(b')=S(a)+S(b)$, but $S(a')=S(a)+1$, contradicting the maximality of $S(a)$.

We conclude that there is a maximizing $a$ with $a\le b$ and $a_2=\ldots=a_d=9$.

What can we gain if we drop the condition $a\le b$?

• If $a_1+b_1\ge 9$, we can let $a_1'=9$ and $b_1'=a_1+b_1-9$, thereby making $a'$ consist only of $9$'s and apparently the largest number $\le n$ of this form

• If $a_1+b_1<9$, we can let $a_1'=0$ and $b_1'=a_1+b_1$, thereby making $a'$ consist only of $9$'s and apparently the largest number $\le n$ of this form

In summary, the $a$ (and associated $b$) found by the greedy method is among the maximizers.