2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – 6005 Aug 27 '16 at 16:33
  • 1
    $\begingroup$ What math olympiad is this from? $\endgroup$ – 6005 Aug 27 '16 at 16:55
  • $\begingroup$ It's from one that my university organized a few years ago. It's just a regional contest. $\endgroup$ – jxm Aug 27 '16 at 19:28
  • $\begingroup$ I've made a new question here asking for an exact maximum value for $S(a + b + c)$ in a more general case. $\endgroup$ – 6005 Aug 30 '16 at 18:17
3
$\begingroup$

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

Why your proof fails

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.

Additional notes

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

$\endgroup$
  • $\begingroup$ my typing speed is a bit faster:) $\endgroup$ – Ignat Domanov Aug 27 '16 at 17:04
  • $\begingroup$ @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. $\endgroup$ – 6005 Aug 27 '16 at 17:10
  • $\begingroup$ Can we make the bound 52 sharp? $\endgroup$ – Ashar Tafhim Aug 27 '16 at 20:12
  • $\begingroup$ @AsharTafhim Good question. I asked about it here. I believe $51$ is the actual maximum. $\endgroup$ – 6005 Aug 27 '16 at 21:17
1
$\begingroup$

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

$\endgroup$

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.