# 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?

• What is $n$ in the requirement $a+b=n$? – 5xum Oct 5 '18 at 11:29
• I assume $n=x$, no? As a small point, you say that you are allowing $b=n$ but that would make $a=0$ which you are not allowing. Do you mean to allow the pair $n+0=n$ or not? – lulu Oct 5 '18 at 11:36
• @5xum, n goes upto $10^{12}$. – Andrew Scott Oct 5 '18 at 11:43
• I think the point isn't so much that the greedy algorithm finds some sort of unique max. Indeed, in most cases it just finds one of many. To prove it, I'd start by noting that given any optimal solution $a≤b$ we can subtract enough from each decimal place of $a$ to make the corresponding place of $b$ equal to $9$ without changing the sum you want. For example, for $n=154$ we could have the solution $77,77$ or we could "move $2$ over from each slot" to get the equivalent solution $55,99$ which is what the greedy algorithm would find. – lulu Oct 5 '18 at 11:45
• @lulu, Yes. I am sorry. Edited the question. – Andrew Scott Oct 5 '18 at 11:46

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.

• WOW. Thanks! :) – Andrew Scott Oct 5 '18 at 12:02

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 with $$b_j>0$$, for otherwise we'd have $$b. If we replace $$a_k$$ with $$a_k+1$$, $$b_j$$ with $$b_j-1$$ and $$b_i$$ with $$9$$ for $$j, 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.