# If the sum of the digits of $a+b, a+c, a+b$ are bounded by $k$, what is the maximum sum of digits of $a+b+c$?

Question: For $n \in \mathbb{N}$, let $S(n)$ denote the sum of the base 10 digits of $n$. Assuming that $a,b,c \ge 0$ and $$S(a+b), S(b+c),S(a+c) \le k,$$ What is the maximum possible value of $S(a+b+c)$ (as a function of $k$)?

This is motivated by this question.

We know that the answer is between $15k-9$ and $15k$, inclusive. Both of these bounds are found by adapting the answers to the motivating question. Specifically, we can achieve $15k-9$ by taking \begin{align*} a &= \underbrace{444\ldots4}_{k-1} \;\underbrace{555\ldots 5}_{k-1}\;\underbrace{555\ldots 5}_{k-1} \;5 \\\ b &= \underbrace{555\ldots 5}_{k-1}\;\underbrace{444\ldots 4}_{k-1}\;\underbrace{555\ldots 5}_{k-1}\;5\\ c &= \underbrace{555\ldots 5}_{k-1}\;\underbrace{555\ldots 5}_{k-1}\;\underbrace{444\ldots 4}_{k-1}\;5. \end{align*} And we can also prove that $S(x+y) \le S(x) +S(y)$ and $S(x) \le 5S(2x)$ (see my answer to the motivating question), so that $$S(a+b+c) \le 5S(2a+2b+2c) \le 5[S(a+b) + S(a+c) + S(b+c)] \le 15k.$$

In the comments, it was also determined that we may assume either $S(a+b) = S(a+c) = S(b+c) = k$ and $S(a+b+c) = 15k$, or $S(a+b) = S(a+c) = k$, $S(b+c) = k-1$, and $S(a+b+c) = 15k - 5$.

I expect we can get an exact answer, and that that answer is $15k - 9$ (for $k \ge 1$).

• Well, lets suppose $S(a+b)=l$,$S(b+c)=m$ and $S(a+c)=n$ w.l.o.g $l \leqslant m \leqslant n \leqslant k$.Then adding $1$ times a very large exponent of ten ,such that we do not have the carry problem, to only one of the $a,b,c$ will increase two of $l,m,n$ by $1$ and $S(a+b+c)$ by $2$.We can use this process to increase values of $l,m,n$ and also the value of $S(a+b+c)$.So first we will apply this method to $c$ n-k times. this will 'make' $n$ into $k$ and increase $m$ also.Doing the same with $b$ will 'make' the new $m$ into $k$.Then using you inequality, we find that new $l$ is $k-1$ or $k$. – Ashar Tafhim Aug 27 '16 at 23:01
• Thus we can consider only two triples for $(l,m,n)$ for maximum value; $(k-1,k,k)$ and $(k,k,k)$.After that i have no idea.:) – Ashar Tafhim Aug 27 '16 at 23:04
• @AsharTafhim That gets us very close actually! Once you can assume $S(a+b) = S(a+c) = S(b+c) = k$, then you can consider that $S(x) \equiv x \pmod{9}$, so that $S(a+b+c) \equiv 15k \pmod{9}$. So the max is either $15k-9$, or $15k$. We just have to rule out $15k$. – 6005 Aug 27 '16 at 23:05
• Well, for $(k,k,k-2)$ , $S(a+b+c) \leqslant 5(l+m+n)=15k-10$ so it cannot be the maximum value,same for other values. – Ashar Tafhim Aug 27 '16 at 23:31
• Another point is that in both case the inequality above becomes an equality. – Ashar Tafhim Aug 27 '16 at 23:35

We will show that the maximum is indeed $15k - 9$.

First, let's investigate the inequalities which you used, and in particular, what the effect is if either is not an equality.

In your previous answer, it was shown that $S(x) \leq 5S(2x)$ essentially by noting that this is true for each digit, and then noting that $S(2x)$ is equal to the sum over the digits $d$ of $x$ of $S(2d)$. Now we note that for individual digits, equality occurs in $S(d) \leq 5S(2d)$ precisely when $d$ is either $0$ or $5$. It follows that if any digit of $x$ (say the digit is $d$) is not $5$ or $0$, then we in fact have that $S(x) \leq 5S(2x) - 5S(2d) + S(d)$. But if $d$ is not $5$ or $0$, then we can check that $5S(2d) - S(d)$ is at least $9$, and so $S(x) \leq 5S(2x) - 9$.

The consequence of this is that if the digits of $a + b + c$ are not each equal to either $5$ or $0$, then we get that $S(a + b + c) \leq 5S(2a + 2b + 2c) - 9 \leq 15k - 9$.

We see that if $S(a + b + c) > 15k - 9$ then the digits of $a + b + c$ is each either $0$ or $5$.

If we look at your proof that $S(x + y) \leq S(x) + S(y)$, we note that equality occurs if and only if there are no carries when adding $x$ and $y$, and that in fact if there are any carries, then we can see that $S(x + y) \leq S(x) + S(y) - 9$. (A carry decreases the sum of the digits by at least $9$.)

We see that if there are any carries involved in adding $a + b$, $b + c$ and $c + a$ to get $2(a + b + c)$, then in fact $$S(a + b + c) \leq 5S(2a + 2b + 2c) \leq 5(S(a + b) + S(b + c) + S(c + a) - 9) \leq 15k - 45.$$

This then shows that if $S(a + b + c) > 15k - 9$, then there are no carries involved in adding together $a + b$, $b + c$ and $c + a$.

Now suppose that $a$, $b$, and $c$ are as in the conditions of the problem, and that $S(a + b + c) > 15k - 9$. We can assume that $a$, $b$ and $c$ do not all end in a zero, as otherwise we could remove the trailing zero from each one. Let $M = a + b + c$, and let $$a = \sum_{i = 0}^\infty a_i 10^i$$ be the decimal expansion of $a$, and analogously for $b$ and $c$.

Since the last digit of $M$ is a $0$ or a $5$, the last digit of $2M$ must be a $0$. Since there are no carries involved in the addition, each of $a + b$, $b + c$, and $c + a$ must end in a $0$. We thus have that each of $a_0 + b_0$, $b_0 + c_0$, and $c_0 + a_0$ must be $0$ or $10$, and they are not all $0$. If, say, $a_0 + b_0$ were $0$, then this would imply $a_0 = b_0 = 0$. But then since at least one of $b_0 + c_0$ and $c_0 + a_0$ is not $0$, we would have that $c_0 = 10$, a contradiction. It follows that $a_0 + b_0 = b_0 + c_0 = c_0 + a_0 = 10$, and so $a_0 = b_0 = c_0 = 5$.

For will now show by induction that for each $n$, we have that $9 \leq a_n + b_n + c_n \leq 19$, and that when adding $a + b + c$ to get $M$, there is a carry of $1$ for each digit. This is true for $n = 0$ as shown above. Now suppose that for some $n$ that the claim is true for $n-1$. We will show that it is also true for $n$.

Since the digits of $M$ are each either $0$ or $5$, we have that the $n^\text{th}$ digit of $2M$ is either a $0$ or a $1$. Since there are no carries involved in the addition of $a + b$, $b + c$ and $c + a$, we have that the $n^\text{th}$ digit of each of $a + b$, $b + c$ and $c + a$ is either a $0$ or a $1$.

Now the $n^\text{th}$ digit of $a + b$ is either the units digit of $a_{n} + b_{n}$, or the units digit of $a_n + b_n + 1$. (The carry for each digit when adding $a$ and $b$ is at most $1$)

We thus have that $a_n + b_n$ must be one of $0, 1, 9, 10$ or $11$. Similarly, each of $b_n + c_n$ and $c_n + a_n$ is one of $0, 1, 9, 10$ or $11$.

Now by the inductive hypothesis, the carry involved when calculating the $n^\text{th}$ digit of $M$ is exactly $1$, and so the $n^\text{th}$ digit of $M$ is equal to the units digit of $a_n + b_n + c_n + 1$. The units digit of this must be either $0$ or $5$, and so we get that $a_n + b_n + c_n$ is one of $4, 9, 14, 19$ or $24$. Thus $2(a_n + b_n + c_n)$ is one of $8, 18, 28, 38$ or $48$. Since $a_n + b_n$, $b_n + c_n$ and $c_n + a_n$ are each at most $11$, we can eliminate $38$ and $48$ as possibilities because they are too large. It is also easy to see that $8$ is not possible, since this would require each of $a_n + b_n$, $b_n + c_n$ and $c_n + a_n$ to be less than $9$, and hence each would be at most $1$.

The remaining possibilities for $2(a_n + b_n + c_n)$ are $18$ and $28$, and so $a_n + b_n + c_n$ is one of $9$ or $14$. Each lies in the range $9$ to $19$, and together with the carry of $1$ from the previous column, we see that there will also be a carry of $1$ into the next column, so our claim is proven.

But the claim above implies that for each $n$, at least one of $a_n$, $b_n$ or $c_n$ is not zero, which is impossible since $a$, $b$, and $c$ are finite. We thus have a contradiction, and hence we must have that $S(a + b + c) \leq 15k - 9$.

• Excellent work! This is a very nice proof. – 6005 Sep 1 '16 at 4:29
• Instead of the induction you did, we can also finish the proof as follows. As you observed, $2a+2b+2c$ is only $0$s and $1$s, so $a+b$, $b+c$, $c+a$ are only zeroes and ones in order to not carry, i.e. they are sums of distinct powers of ten. In order to add to $2a+2b+2c$, they must not share any powers of ten. So let's say $a+b$ contains the biggest power of ten, then $(a+b) - (a+c) - (b+c) > 0$ so $c < 0$, contradiction. – 6005 Sep 1 '16 at 4:41
• In any case, it is therefore critical to the proof that $a, b, c \ge 0$. We may observe that $15k$ is possible if $a, b, c$ are arbitrary integers. Because then we can just take $a, b, c$ so that $a+b = 10^1 + 10^4 + \cdots + 10^{3k-2}$, $a+c = 10^2 + 10^5 + \cdots + 10^{3k-1}$, $b+c = 10^3 + 10^6 + \cdots + 10^{3k}$ and we get $S(a+b+c) = 15k$. – 6005 Sep 1 '16 at 4:43