1

Given $N$, we have to represent $N$ = $A$ + $B$, where $A$ and $B$ are positive integers. The task is to find the minimum sum of digits of $A$ + sum of digits of $B$.

For example: $N = 15$, it can be represented $A = 1, B = 14$, where the sum of digits = $6$, which is the minimum sum of digits I can get.

I just noticed that the answer is the sum of digits of $N$ if $N$ is not a power of ten, otherwise the answer is $10$.

Why is this true?

Mohamed Magdy
  • 673

2 Answers2

1

Let $a_i,b_i\in\{0,\ldots,9\}$ be the decimal digits of $A$ and $B$ $$A=\sum_{i=0}^aa_i10^i, \qquad\text{ and }\qquad B=\sum_{i=0}^bb_i10^i,$$ with $a_a\neq0$ and $b_b\neq0$. Then the digit sums of $A$ and $B$ are $$\sigma(A)=\sum_{i=0}^aa_i, \qquad\text{ and }\qquad \sigma(B)=\sum_{i=0}^bb_i.$$ Without loss of generality $B\leq A$, so that $b\leq a$, and hence setting $b_i:=0$ for $i>b$ yields $$A+B =\sum_{i=0}^aa_i10^i+\sum_{i=0}^bb_i10^i =\sum_{i=0}^a(a_i+b_i)10^i =\sum_{i=0}^cc_i10^i,$$ for some uniquely determined $c_i\in\{0,\ldots,9\}$, and the digit sum of $A+B$ equals $$\sigma(A+B)=\sum_{i=0}^cc_i.$$ Now we can carry out the addition place by place as we learned in elementary school. Let $x_i\in\{0,1\}$ denote the carry to the $i$-th place, so that in particular $x_0=0$, and $x_{i+1}=1$ if and only if $a_i+b_i+x_i>9$. Then we can distinguish two cases:

  1. If $a_i+b_i+x_i\leq9$ then $c_i=a_i+b_i+x_i$, and $x_{i+1}=0$. The digit sum remains unchanged.
  2. If $a_i+b_i+x_i>9$ then $c_i=a_i+b_i+x_i-10$ and $x_{i+1}=1$. The digit sum decreases by $9$.

This shows that $\sigma(A+B)\leq\sigma(A)+\sigma(B)$, and equality holds if and only if there are no carries.

Given $N=\sum_{i=0}^nn_i10^i$ with $n_i\in\{0,\ldots,9\}$ and $n_n\neq0$ we can take $$A=10^n\qquad\text{ and }\qquad B=N-A,$$ to achieve $\sigma(N)=\sigma(A)+\sigma(B)$, as there are clearly no carries. This example fails if and only if $B=0$, i.e. if and only if $N=10^n$ for some $n\in\Bbb{N}$.

If $N=10^n$ then $A=B=5\cdot10^{n+1}$ shows that the minimum sum of digit sums is at most $10$. If the digit sums of $A$ and $B$ are less than $10$ then $A=k\cdot 10^a$ and $B=l\cdot10^b$ for some $a,b\in\Bbb{N}$ and $k,l\in\{1,\ldots,9\}$ and hence to get $A+B=10^n$ we must have $a=b=n-1$ and $k+l=10$, which shows that the minimum sum of digit sums is indeed $10$.

Finally, note that if $n=0$ then $N=10^0=1$ then $N$ cannot be written as the sum of two positive integers, and hence the minimum does not exist.

Servaes
  • 63,261
  • 7
  • 75
  • 163
0

Let our number be written as: $$N=x_1x_2x_3x_4\ldots x_n$$

(Note: this is concatenation, not multiplication)

Then $\forall i; 0\leq x_i \leq 9$

and we may easily pick two numbers $$A=a_1a_2\ldots a_n$$ and $$B=b_1b_2\ldots b_n$$ (with the same constraints) such that $$\forall i; a_i +b_i = x_i$$ The digit sum remains consistent on account of this, i.e. $$digsum(N)=digsum(A)+digsum(B)$$

For $N=10^k$, we take $A=9(10^{k-1})$, and $B = 10^{k-1}$ for an easy solution. It can't be $1$ because of the $A,B>0$ requirement, so it must be the next power of ten up.

Rhys Hughes
  • 12,842
  • How have you proved that these are minimal? – Peter Foreman Apr 15 '19 at 20:58
  • The first case is minimal because at each position your sum is just $x_i$ and not greater.(For example, if you do $177$, writing as $134+43$ would be minimal, but $96+81$ causes carry over in the tens and would thus have a digsum which is larger. The second case follows this but the would-be minimal case is impossible so one has to settle for second best. – Rhys Hughes Apr 15 '19 at 21:04