1
$\begingroup$

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$).

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Ashar Tafhim Aug 27 '16 at 23:01
  • $\begingroup$ 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.:) $\endgroup$ – Ashar Tafhim Aug 27 '16 at 23:04
  • 1
    $\begingroup$ @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$. $\endgroup$ – 6005 Aug 27 '16 at 23:05
  • 1
    $\begingroup$ 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. $\endgroup$ – Ashar Tafhim Aug 27 '16 at 23:31
  • 1
    $\begingroup$ Another point is that in both case the inequality above becomes an equality. $\endgroup$ – Ashar Tafhim Aug 27 '16 at 23:35
3
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Excellent work! This is a very nice proof. $\endgroup$ – 6005 Sep 1 '16 at 4:29
  • 1
    $\begingroup$ 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. $\endgroup$ – 6005 Sep 1 '16 at 4:41
  • 1
    $\begingroup$ 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$. $\endgroup$ – 6005 Sep 1 '16 at 4:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.