# if the sum of the digits of $a+b$, $b+c$ and $a+c$ is $<5$, then is the sum of the digits of $a+b+c$ less or equal than 50?

This is a problem from a math olympiad:

Let $S(x)$ denote the sum of the digits of a natural number $x$ in its decimal representation. Do there exist three natural numbers $a$, $b$ and $c$ with $S(a+b)<5$, $S(a+c)<5$, $S(b+c)<5$ and $S(a+b+c)>50$?

My attempt:

NOTATION: Given a real number $x$, $[x]$ is the integer part of $x$.

REMARK 1: Let $x$ be a natural number with $2$ digits. Then the sum of its two digits is $$\left[\frac{x}{10}\right]+x-\left[\frac{x}{10}\right]\cdot 10=x-9\cdot \left[\frac{x}{10}\right].$$

REMARK 2: If $x$ is a real number with $\left[ x\right]\geq1$, then $\left[ 2x\right]\leq 3\left[ x\right]$.

Let $a$, $b$ and $c$ be any natural numbers. Write $$a=\sum_{i=0}^{n-1}a_i 10^i,\quad b=\sum_{i=0}^{n-1}b_i 10^i, \quad c=\sum_{i=0}^{n-1}c_i 10^i,$$ where $a_i,b_i,c_i\in\{0,\ldots,9\}$ and $a_n\neq0$ or $b_n\neq0$ or $c_n\neq0$. By Remark 1, $$S(a+b+c)=\sum_{i=0}^{n-1}\left(a_i+b_i+c_i-9\cdot \left[ \frac{a_i+b_i+c_i}{10}\right]\right),$$ $$S(a+b)=\sum_{i=0}^{n-1}\left(a_i+b_i-9\cdot \left[ \frac{a_i+b_i}{10}\right]\right),$$ $$S(b+c)=\sum_{i=0}^{n-1}\left(b_i+c_i-9\cdot \left[ \frac{b_i+c_i}{10}\right]\right),$$ $$S(a+c)=\sum_{i=0}^{n-1}\left(a_i+c_i-9\cdot \left[ \frac{a_i+c_i}{10}\right]\right).$$ By Remark 2, if $\left[ (a_i+b_i+c_i)/10\right]\geq1$, then $$3\left[(a_i+b_i+c_i)/10\right]\geq \left[ 2(a_i+b_i+c_i)/10\right]\geq \left[ (a_i+b_i)/10\right]+\left[ (b_i+c_i)/10\right]+\left[ (a_i+c_i)/10\right].$$ Thus, \begin{align*} S(a+b+c)= {} & \sum_{i=0}^{n-1}\left(a_i+b_i+c_i-9\cdot \left[ \frac{a_i+b_i+c_i}{10}\right]\right) \\\\ = {} & \frac12\sum_{i=0}^{n-1}(a_i+b_i)+\frac12\sum_{i=0}^{n-1}(b_i+c_i)+\frac12\sum_{i=0}^{n-1}(a_i+c_i)\\ &\qquad-9\sum_{\substack{{0\leq i\leq n-1}\\{(a_i+b_i+c_i)/10\geq1}}}\left[ \frac{a_i+b_i+c_i}{10}\right] \\\\ \leq {} & \frac12\sum_{i=0}^{n-1}(a_i+b_i)+\frac12\sum_{i=0}^{n-1}(b_i+c_i)+\frac12\sum_{i=0}^{n-1}(a_i+c_i)-3\sum_{i=0}^{n-1}\left[ \frac{a_i+b_i}{10}\right]\\ &\qquad-3\sum_{i=0}^{n-1}\left[ \frac{b_i+c_i}{10}\right]-3\sum_{i=0}^{n-1}\left[ \frac{a_i+c_i}{10}\right] \\\\ = & \frac12\sum_{i=0}^{n-1}\left(a_i+b_i-6\left[ \frac{a_i+b_i}{10}\right]\right)+\frac12\sum_{i=0}^{n-1}\left(b_i+c_i-6\left[ \frac{b_i+c_i}{10}\right]\right)\\ &\qquad+\frac12\sum_{i=0}^{n-1}\left(a_i+c_i-6\left[ \frac{a_i+c_i}{10}\right]\right) \\\\ = {} & \frac{S(a+b)+S(b+c)+S(a+c)}{2}+\frac{3}{2}\sum_{i=0}^{n-1}\left[ \frac{a_i+b_i}{10}\right]\\ &\qquad+\frac{3}{2}\sum_{i=0}^{n-1}\left[ \frac{b_i+c_i}{10}\right]+\frac{3}{2}\sum_{i=0}^{n-1}\left[ \frac{a_i+c_i}{10}\right] \\\\ \leq {} & \frac{S(a+b)+S(b+c)+S(a+c)}{2}+\frac{3}{2}S(a+b)+\frac{3}{2}S(b+c)+\frac{3}{2}S(a+c) \\\\ = {} & 2(S(a+b)+S(b+c)+S(a+c))\;. \end{align*} Then, if $S(a+b)<5$, $S(a+c)<5$, $S(b+c)<5$, we have $S(a+b+c)<2(5+5+5)=30$.

• Surprisingly tricky! I can show relatively simply that $S(a+b+c) \le 60$. But getting below $50$ may require something closer to what you're doing. – 6005 Aug 27 '16 at 16:33
• What math olympiad is this from? – 6005 Aug 27 '16 at 16:55
• It's from one that my university organized a few years ago. It's just a regional contest. – jxm Aug 27 '16 at 19:28
• I've made a new question here asking for an exact maximum value for $S(a + b + c)$ in a more general case. – 6005 Aug 30 '16 at 18:17

The answer to the question in the title is no -- it is possible that $S(a+b+c) = 51$. In particular, your proof is incorrect.

Take \begin{align*} a &= 545\;545\;545\;5 \\ b &= 554\;554\;554\;5 \\ c &= 455\;455\;455\;5. \end{align*} (Spaces to aid readability, so you can tell what's going on here.) Then we have \begin{align*} a+b &= 1\;100\;100\;100\;0 \\ a+c &= 1\;001\;001\;001\;0 \\ b+c &= 1\;010\;010\;010\;0 \\ \end{align*} So $S(a+b) = S(a+c) = S(b+c) = 4 < 5$.

But $$a+b+c = 1\;555\;555\;555\;5$$ so $S(a+b+c) = 51$.

The error is in the beginning, in asserting that the sum of digits of $S(a+b+c)$ is equal to $\sum_i S(a_i + b_i + c_i)$, and similar for $a+b$,$a+c$, and $b+c$. While $S(a+b+c) \le \sum_i S(a_i + b_i + c_i)$, they certainly need not be equal. Replacing it with $\le$ instead of $=$, you can see that your proof no longer goes through.

Also note that if you use $S(a+b), S(a+c), S(b+c) \le 4$ at the end instead of $S(a+b), S(a+c), S(b+c) < 5$, then your proof would purport to show $S(a+b+c) \le 2 (12) = 24$, which has even simpler counterexamples.

While it is not true that $S(a+b+c) \le 50$, it is still true that $S(a+b+c) \le 60$. Here is a proof.

First, we can note that $$S(x + y) \le S(x) + S(y). \tag{1}$$ To prove it, first imagine adding $x$ and $y$ in base 10 without carrying. Then the sum of digits stays the same. But each time we carry, we reduce the sum. So $x+y$ after all carrying is completed must have a smaller sum of digits.

A second observation is that $$S(2x) \ge \frac15 S(x) \tag{2}$$

To prove it, first consider what multliplication by $2$ does to single digits: $1 \mapsto 2$, $2 \mapsto 4$, $3 \mapsto 6$, $4 \mapsto 8$, $5 \mapsto 10$, $6 \mapsto 12$, $7 \mapsto 14$, $8 \mapsto 16$, $9 \mapsto 18$. In every case, the sum of digits is at least $\frac{1}{5}$ of the original digit (the worst case being the digit $5$ becoming $10$). Then notice (and this is special to multiplication by $2$ in particular) that to find $2x$, we may multiply each digit by $2$ individually, resulting in a one or two digit number for each digit, and then add all these up with no carrying. In other words, $S(2x)$ is the sum over digits $d$ of $x$ of $S(2d)$. Since $S(2d) \ge \frac{1}{5}$, it follows that $S(2x) \ge \frac{1}{5} S(x)$.

Putting (2) and (1) together, in that order: $$S(a+b+c) \le 5S(2(a+b+c)) \le 5\left[S(a+b) + S(b+c) + S(a+c)\right] \le 5\left[4 + 4 + 4\right] = 60.$$

• my typing speed is a bit faster:) – Ignat Domanov Aug 27 '16 at 17:04
• @Ignat Because you did not type as much :) Nice work finding the counterexample though. I originally tried $55505550455, 55504550555, 45505550555$ which is still a counterexample to OP's proof but not to the original problem. – 6005 Aug 27 '16 at 17:10
• Can we make the bound 52 sharp? – Ashar Tafhim Aug 27 '16 at 20:12
• @AsharTafhim Good question. I asked about it here. I believe $51$ is the actual maximum. – 6005 Aug 27 '16 at 21:17

Counterexample (the sum is 51):

a = 555 444 555 5

b = 555 555 444 5

c = 444 555 555 5

a+b = 1111 000 000 0

a+c = 1000 000 111 0

b+c = 1000 111 000 0

a+b+c = 1555 555 555 5