# Logic problem involving sum of digits

Good one guys! I'm studying to the national maths olympiad (brazil) by myself, and I ran up to the following question:

Let $S(n)$ be the sum of the digits of n. For example $S(77) = 14$ and $S(2003) = 5$ . Tell if there is a n that is integer, and positive with :

$S(n) = 9$

&

$S(n^2) = 81$

I found a number, it is $111 111 111$ ( 9 times de digit 1), but it was just a lucky guess.

I want to go deeper into the exercise and know if there are ways to calculate it (without lucky guesses) using logic or any concept from maths.

• @DonkeyKong No, it would be taking the sum of the digits of $111,111,111^2$, or $12,345,678,987,654,321$ – Mike Jun 30 '15 at 1:33
• @Donkey Kong: No, $S(n^2)$ means squaring the number $n$ and then taking the sum of digit. – miracle173 Jun 30 '15 at 1:33
• $111111111^2=12345678987654321$ and the sum of its digits is $81$. – Michael Burr Jun 30 '15 at 1:35
• $11101110111^2=123234645696546432321$ is another one – miracle173 Jun 30 '15 at 1:48
• The question seems to be how can you square $n$ without getting any carries? Only thing I can see to narrow things down is $n$ must have at least $5$ digits. It takes at least $9$ digits to have a digital sum of $81$. – Mike Jun 30 '15 at 1:49

Only a sketch: one can prove that

$$s(x+y) \le s(x)+s(y)$$ Equality holds if and only if no carry occurs when adding the digits.
So if $x=\sum 10^i x_i$ and $y= \sum 10^i y_i$ then equality holds if and only if $x_i+y_i<=9$ for all $i$.

$$s(xy)<=s(x)s(y)$$ Equality holds if and only if: no digit product is larger than $9$ and no carry occurrs while adding the digit products, so $x_j y_{i-j}<=9$ for all possible $i,j$ and $\sum_j x_j y_{i-j}<=9$. Therefore $s(n^2)<=s(n)^2$ and if $s(n)=9$ then $s(n^2)<=81$

So the number cannot contain a digit larger than $3$ because then the square of the digit is larger than $9$. Also if $x_i$ and $x_j$ are two digits and $x_i\ge 3$ and $x_j \gt 1$ then $x_i x_j+x_j x_i \ge 12$. This is larger than 9 and therefore cannot happen.

• So we have only the following possibilities:
• $n$ contains only the digits $0$ and $1$ and $2$
• $n$ contains the digits $0$ and $1$ and exactly one digit $3$.

So besides $0$ we can have the following digits

$$1,1,1,1,1,1,1,1,1$$ $$1,1,1,1,1,1,1,2$$ $$1,1,1,1,1,1,2,2$$ $$1,1,1,2,2,2$$ $$1,2,2,2,2$$ $$1,1,1,1,1,1,3$$

If we position nonzero digits only at the digit positions $$1,3,7,15,31,\ldots,2^k-1,\ldots$$ then we can guarantee that the product contains only digitsums of the form $(x_i)^2$ (at position $2i$) and $2x_i x_j$ (at position i+j). So no carry will occur. So for each digit tuple above we can construct a number with $s(n)=9$ and $s(n^2)=81$, e.g for $1,2,2,2,2$ we can construct $$20000000000000002000000020002010$$ (we can also use a permutation of these digits, e.g $2,2,1,2,2$) This will be a number with the desired property.If one adds $0$, it will be a valid number, too. But one can try to construct smaller numbers by removing some of the $0$. As long as no carry occurs, this will be a valid number.

• A couple things to add. Using all ones is the simplest solution as there can never be any carries: the product could be written as the sum of $9$ numbers each with a maximum digit of $1$. Also, you can use the units digit. So $1,000,000,020,002,022$ works. – Mike Jun 30 '15 at 4:33
• @Mike: you are right, but I mentioned that one can construct other solutions by adding/removing zeros – miracle173 Jun 30 '15 at 12:56

Consider numbers with just three digits:

$n = a 100 + b 10 + c$, where $S(n) = a + b + c = 9$.

$n^2 = a^2 10^4 + a b 10^3 + (b^2 + 2 a c) 10^2 + 2 b c 10 + c^2$ where now $S(n^2) = a^2 + a b + (b^2 + 2 a c) + 2 b c + c^2 = 81$.

Set up some equations!

You can generalize this to larger numbers, if needed.

Good luck on the Olympiad!

• Why is this the sum of the coefficients? I looks like you're assuming that all of the coefficients of the powers of $10$ are at most $9$ (after performing the products) – Michael Burr Jun 30 '15 at 1:28
• For example, if $n=333$, then $a=3$, $b=3$, and $c=3$. Then $n^2=110889$. Then $S(n^2)=27$. However, your formula for $S(n^2)$ gives $72$. – Michael Burr Jun 30 '15 at 1:30