Show that for any positive integer k, the sum of the digits of any multiple of $10^k-1$ is at least $9k$.
It is clearly sufficient to deal with nonnegative multiples, since if $S(x)$ is the sum of digits of the integer x, then $S(x)=S(-x)$ for any integer x. The claim holds for $k=1$ because all positive multiple of $9$ have sum of digits equal to a positive multiple of $9$, and hence the sum of the digits is at least $9$. We know that $S(x+y) \leq S(x)+S(y)$ for all nonnegative integers x and y. Also, $S(x)\leq x$ for all nonnegative x with equality iff $0\leq x\leq 9$.
I'm not sure if the sum of the digits of any multiple of $10^k-1$ is always a multiple of $9k$.
We need to show that $S(a(10^k-1)) \equiv 0\mod 9k$ for all $k\ge 1, a \in \mathbb{Z}$.
Let N be a positive integer with $N>10^k.$ I think we can show there is some integer $M<N$ congruent to $N$ modulo $10^k-1$ with $S(M)\leq S(N)$. Then from this result, we can solve the question by induction; $S(10^k-1) = 9k$ and if for some multiple $N > 10^k-1,$ we assume that $S(M) \ge 9k$ for all multiples smaller than $N$, then the given claim shows that there is a multiple $M < N$ of $10^k-1$ so that $S(M)\leq S(N)$, from which the result follows. Write $N = q(10^k-1) + r$ where $r < 10^k – 1$. Suppose for a contradiction that there is some $N > 10^k$ so that for all $M < N$ with $M \equiv N\mod 10^k-1$, we have $S(M) > S(N).$ The sum of the digits of a nonnegative integer is equivalent to its remainder modulo 9. There might be a useful formula involving the sum of digits of the sum of two numbers and the number of carries when addition is done between them.
Best Answer
Suppose $N$ is the least positive multiple of $10^k-1$ which achieves the minimum digit sum.
We claim that this forces $N \le 10^k-1$; if this were not true, we could write $N = A\cdot 10^k + B$ with $B < 10^k$ ($B$ holds the last $k$ digits of $N$ and $A$ holds the rest). Then $A+B$ would also be a positive multiple of $10^k-1$, which is strictly smaller than $N$ (since $N \ge 10^k$), and $S(A+B) \le S(A) + S(B) = S(N)$, contradicting the assumption that $N$ is the smallest specimen with minimum digit sum.
Thus, $N$ has at most $k$ digits, and being a positive multiple of $10^k-1$ must be exactly $10^k-1$, which has $S(N) = 9k$.