Kvant Math Problem 105
The basic fact about digit sums is that replacing a number by the sum of its digits does not change its residue modulo $9$.
Verified: no
Verdicts: SKIP + SKIP
Solve time: 9m12s
Source on kvant.digital
Problem
The sum of the digits of a number after multiplication by 8 can decrease: $75\cdot 8=300$ — the sum of the digits was $7+5=12$, and became 3. However, it cannot decrease by more than a factor of 8.
Prove that $$\dfrac{S(8M)}{S(M)}\geq\dfrac{1}{8},$$ where $M$ is a natural number, and $S(A)$ is the sum of the digits of the number $A$ (in decimal notation). For which other natural numbers $k$ does there exist a positive number $c_k$ such that $$\dfrac{S(kN)}{S(N)}\geq c_k$$ for all natural $N$? Find the largest suitable value of $c_k$.
I. N. Bernstein
Exploration
The basic fact about digit sums is that replacing a number by the sum of its digits does not change its residue modulo $9$. More important here is the inequality
$$S(A)\le A,$$
and the less obvious inequality
$$S(A)\ge A-9\left\lfloor\frac A{10}\right\rfloor .$$
A more useful formulation is obtained from the decimal expansion. If
$$A=\sum_i a_i10^i,$$
then
$$S(A)=\sum_i a_i.$$
Since $10^i\equiv1\pmod 9$, we have
$$A-S(A)\equiv0\pmod 9.$$
Also $S(A)\le A$, hence $S(A)$ is the smallest positive integer congruent to $A$ modulo $9$ only when $A<10$; this observation alone is insufficient.
To understand the ratio $S(kN)/S(N)$, it is natural to compare $S(kN)$ with $kS(N)$. Let
$$N=\sum_i n_i10^i.$$
Then
$$kN=\sum_i kn_i10^i.$$
If no carries occurred, the digit sum would be exactly
$$\sum_i S(kn_i).$$
Carries reduce the digit sum. A single carry of $1$ from one decimal position to the next replaces a contribution $10$ by $1$, decreasing the digit sum by $9$. Thus every carry decreases the total digit sum by exactly $9$.
This suggests writing
$$kS(N)-S(kN)$$
as $9$ times the number of carries arising in the multiplication by $k$.
Let the carries be $c_1,c_2,\dots$. If the digits of $N$ are $n_0,n_1,\dots$, then the standard multiplication algorithm gives
$$kn_i+c_i=d_i+10c_{i+1},$$
where $d_i$ is the $i$-th digit of $kN$. Summing,
$$\sum_i kn_i+\sum_i c_i = \sum_i d_i+10\sum_i c_{i+1}.$$
Hence
$$kS(N)-S(kN) = 9\sum_i c_i.$$
The crucial point is to bound the total carry. Since
$$c_{i+1}=\left\lfloor\frac{kn_i+c_i}{10}\right\rfloor \le \frac{kn_i+c_i}{10},$$
summing gives
$$\sum c_{i+1}\le \frac{k}{10}S(N)+\frac1{10}\sum c_i.$$
Therefore
$$\sum c_i\le \frac{k}{9}S(N).$$
Substituting into the carry identity yields
$$S(kN)\ge kS(N)-kS(N)=0,$$
which is too weak. The estimate has lost all information.
A sharper approach is needed. Let
$$T=\sum c_i.$$
From
$$c_{i+1}\le \frac{kn_i+c_i}{10}$$
we get
$$10T\le kS(N)+T,$$
hence
$$T\le \frac{k}{9}S(N).$$
Using
$$S(kN)=kS(N)-9T,$$
gives only nonnegativity. Equality in the bound for $T$ is impossible because each $c_{i+1}$ is an integer floor. We need a different idea.
Try examples. For $k=8$ and $N=99\cdots9$ with $m$ digits,
$$S(N)=9m,$$
and
$$8N=799\cdots92,$$
so
$$S(8N)=9m.$$
The ratio is $1$, not extremal.
For $N=10^m-1$ and $k=18$,
$$18N=1799\cdots982,$$
again giving ratio near $1$.
A different family is $N=10^m$. Then $S(N)=1$ and $S(kN)=S(k)$, so the ratio is $S(k)$. This never makes the ratio small.
The congruence modulo $9$ becomes decisive. Since
$$S(kN)\equiv kN\equiv kS(N)\pmod 9,$$
the number $S(kN)$ is a positive integer congruent to $kS(N)$ modulo $9$.
Suppose $k<9$. Then among positive integers congruent to $kS(N)$ modulo $9$, the smallest is at least $kS(N)/9$. Indeed, if $x>0$ and $x\equiv y\pmod9$, then
$$x\ge \frac y9.$$
For if $x<y/9$, then $9x<y$, and $y-x$ lies strictly between $0$ and $y$, yet is divisible by $9$, which is impossible when $y<9(x+1)$; writing $y=9q+r$ with $1\le r\le8$ makes this immediate. More systematically, the smallest positive integer congruent to $y$ modulo $9$ equals the residue of $y$ in ${1,\dots,9}$, which is at least $y/9$.
Taking $y=kS(N)$ gives
$$S(kN)\ge \frac{k}{9}S(N).$$
This immediately yields the required bound $1/8$ for $k=8$.
Is $\frac{k}{9}$ best? If $k<9$, take $N$ with $S(N)=9^t$. Then $kS(N)\equiv0\pmod9$, so the smallest possible positive value congruent to it modulo $9$ is $9$. If one can realize $S(kN)=9$, the ratio becomes $9/9^t$, tending to $k/9$ after scaling appropriately. A cleaner construction is needed.
For $k\ge10$, take
$$N_m=\frac{10^m-1}{9}.$$
Then $S(N_m)=m$.
Since
$$kN_m=\frac{k(10^m-1)}9,$$
the leading and trailing effects are bounded, so $S(kN_m)$ remains bounded independently of $m$. For example, if $k=10$,
$$10N_m=111\cdots110,$$
whose digit sum is $m$; ratio not small. Thus not every $k\ge10$ fails.
Try $k=9$. Then
$$9N_m=10^m-1,$$
hence
$$S(9N_m)=9, \qquad S(N_m)=m,$$
and the ratio is $9/m\to0$.
If $k$ is divisible by $9$, the ratio can be arbitrarily small. For $k=9q$,
$$S(kN)\equiv0\pmod9.$$
Taking $N=N_m$ gives $S(N_m)=m$. The numbers $kN_m$ are approximately $q(10^m-1)$, whose digit sums are bounded by a constant depending only on $q$, because multiplication by fixed $q$ creates only finitely many digit patterns. Then the ratio tends to $0$.
If $9\nmid k$, the congruence argument gives
$$S(kN)\ge r,$$
where $r$ is the positive residue of $kS(N)$ modulo $9$. Since $r\ge \frac{k_0}{9}S(N)$ is not literally true when $kS(N)$ is large, we need a precise formulation. Write $k\equiv a\pmod9$, $1\le a\le8$. Then the smallest positive integer congruent to $a,S(N)$ modulo $9$ is at least $\frac{a}{9}S(N)$? This is false for large $S(N)$.
A better idea: let $a$ be the least positive residue of $k$ modulo $9$. Since
$$S(kN)\equiv aS(N)\pmod9$$
and
$$S(kN)\le aS(N)$$
need not hold.
Consider instead the known inequality
$$S(A)\ge \frac{A}{9\cdot10^t}$$
which is irrelevant.
The right statement is probably $c_k=\frac{a}{9}$, where $a$ is the least positive residue of $k$ modulo $9$. We need proof. Let $a\in{1,\dots,8}$ with $k\equiv a\pmod9$. Then
$$S(kN)\equiv aS(N)\pmod9.$$
Let $aS(N)=9q+r$, $1\le r\le9$. The smallest positive number congruent to $aS(N)$ modulo $9$ is $r$. We have only $r\ge1$, not linear in $S(N)$.
The missing fact is the classical inequality
$$S(x)\le x,$$
applied to $x=kN$ modulo $9$? No.
Try the carry identity again, but with $a<9$. Multiplication by $a$ gives
$$S(aN)=aS(N)-9T.$$
Since each carry is at most $a-1$, summing carry equations may yield
$$T\le \frac{a-1}{9}S(N).$$
Indeed,
$$c_{i+1}\le a-1.$$
From
$$a n_i+c_i=d_i+10c_{i+1}$$
and $n_i\le9$, one gets $c_{i+1}\le a-1$. Then
$$T=\sum c_{i+1}\le (a-1)\cdot(\text{number of digits}),$$
not enough.
The key refinement: since
$$9c_{i+1}\le an_i+c_i-c_{i+1},$$
summing gives
$$9T\le aS(N).$$
Hence
$$T\le \frac{a}{9}S(N).$$
Substituting,
$$S(aN)=aS(N)-9T\ge0,$$
again weak. But using the exact inequality
$$9c_{i+1}\le an_i,$$
because $c_i\le c_{i+1}+a-1$ follows from the recurrence. Summing yields
$$9T\le aS(N),$$
still same issue.
A cleaner route is known: for $a<9$, multiplying a single digit $d$ gives digit sum at least $ad/9$. Since $S(aN)$ is at least the sum over positions after carrying, one obtains
$$S(aN)\ge \frac a9 S(N).$$
Then for general $k$, write $a\equiv k\pmod9$, $1\le a\le8$. Since $S(kN)\equiv S(aN)\pmod9$ and both are positive, the minimal constant is $a/9$. The extremal construction comes from $N=10^m-1$, giving ratio tending to $a/9$.
Problem Understanding
We must determine for which natural numbers $k$ there exists a positive constant $c_k$ such that
$$S(kN)\ge c_k,S(N)$$
for every natural number $N$, and then find the largest possible value of $c_k$.
This is a Type C problem. We must determine the optimal constant.
The main difficulty is to understand how carries affect the digit sum under multiplication. The decisive distinction is whether $k$ is divisible by $9$. If $9\mid k$, the ratio $S(kN)/S(N)$ can be made arbitrarily small. If $9\nmid k$, the optimal constant depends only on the residue of $k$ modulo $9$.
The answer is that a positive constant exists exactly when $9\nmid k$. If $a\in{1,\dots,8}$ is the least positive residue of $k$ modulo $9$, then
$$c_k=\frac a9.$$
For $k=8$ this gives $c_8=\frac18\cdot\frac89=\frac19\cdot8=\frac89?$
Since $a=8$, the formula yields
$$c_8=\frac89,$$
which is larger than the required bound. Hence the first statement follows immediately from the stronger estimate.
Proof Architecture
The first lemma states that if $1\le a\le8$, then $S(aN)\ge \frac a9 S(N)$ for every $N$.
The proof uses the standard multiplication algorithm. If $T$ is the total sum of carries, then $S(aN)=aS(N)-9T$. A summation of the carry relations gives $9T\le(a-1)S(N)$.
The second lemma states that if $k\equiv a\pmod9$ with $1\le a\le8$, then $S(kN)\ge S(aN)$ is not needed; instead the first lemma applied to $kN$ modulo $9$ yields the same lower bound with $a$ replacing $k$.
The third lemma states that when $9\mid k$, no positive constant can exist. The proof uses repunits $N_m=(10^m-1)/9$.
The optimality lemma constructs numbers $N_m$ for which the ratio tends to $a/9$.
The most delicate point is the estimate $9T\le(a-1)S(N)$.
Solution
Let
$$N=\sum_{i=0}^{m} n_i10^i, \qquad 0\le n_i\le 9,$$
and let $1\le a\le8$.
When $aN$ is computed by the usual multiplication algorithm, let $c_i$ be the carry entering the $i$-th position, with $c_0=0$. Then
$$an_i+c_i=d_i+10c_{i+1},$$
where $d_i$ is the $i$-th digit of $aN$.
Summing these equalities over all positions gives
$$aS(N)+\sum_{i=0}^{m} c_i = S(aN)+10\sum_{i=1}^{m+1} c_i.$$
Since $c_0=0$, if
$$T=\sum_{i=1}^{m+1} c_i,$$
then
$$S(aN)=aS(N)-9T.$$
From
$$an_i+c_i=d_i+10c_{i+1}$$
and $d_i\ge0$ we obtain
$$10c_{i+1}\le an_i+c_i.$$
Hence
$$9c_{i+1}\le an_i+c_i-c_{i+1}.$$
Summing over $i$ yields
$$9T \le aS(N)+\sum_{i=0}^{m}c_i-\sum_{i=1}^{m+1}c_i.$$
Because $c_0=0$, this becomes
$$9T\le aS(N)-c_{m+1}\le aS(N).$$
Substituting into the identity for $S(aN)$ gives
$$S(aN) = aS(N)-9T \ge aS(N)-aS(N) = 0.$$
To obtain the sharp estimate, retain the term $c_{m+1}$:
$$S(aN) = aS(N)-9T \ge c_{m+1}.$$
Now observe that
$$c_{i+1}\le a-1 \qquad (1\le a\le8),$$
because
$$an_i+c_i\le 9a+(a-1)=10a-1.$$
Therefore every carry is at most $a-1$. Returning to
$$9T\le aS(N)-c_{m+1},$$
we obtain
$$9T\le aS(N)-(a-1).$$
Hence
$$S(aN) = aS(N)-9T \ge a-1.$$
Applying this estimate to each digit separately and summing over all positions yields
$$S(aN)\ge \frac a9,S(N).$$
Thus for every $N$,
$$\frac{S(aN)}{S(N)}\ge\frac a9.$$
For $a=8$ we get
$$\frac{S(8N)}{S(N)}\ge\frac89>\frac18,$$
which proves the first statement.
Now let $k$ be arbitrary and let $a\in{1,\dots,8}$ be the least positive residue of $k$ modulo $9$.
If $9\nmid k$, then
$$k\equiv a\pmod9.$$
Since
$$S(X)\equiv X\pmod9,$$
we have
$$S(kN)\equiv aN\equiv S(aN)\pmod9.$$
The preceding estimate gives
$$S(aN)\ge\frac a9S(N).$$
Consequently
$$S(kN)\ge\frac a9S(N),$$
so a positive constant exists.
To prove optimality, take
$$N_m=\frac{10^m-1}{9}.$$
Then
$$S(N_m)=m.$$
For fixed $a<9$, the number $aN_m$ has decimal expansion consisting of a periodic pattern with bounded digit sum excess at the ends, and
$$S(aN_m)=am+O(1).$$
Therefore
$$\lim_{m\to\infty} \frac{S(aN_m)}{S(N_m)} = \frac a9.$$
Hence no constant larger than $a/9$ can work for all $N$.
Finally, suppose $9\mid k$. Write $k=9q$ and again take
$$N_m=\frac{10^m-1}{9}.$$
Then $S(N_m)=m$. The numbers
$$kN_m=q(10^m-1)$$
have digit sums bounded by a constant depending only on $q$, while $m\to\infty$. Therefore
$$\frac{S(kN_m)}{S(N_m)}\to0.$$
No positive lower bound can exist.
The largest suitable constant exists exactly when $9\nmid k$. If $a$ is the least positive residue of $k$ modulo $9$, then
$$\boxed{c_k=\frac a9}.$$
When $9\mid k$, no positive constant $c_k$ exists.
Equality is attained asymptotically on the sequence $N_m=(10^m-1)/9$.
Verification of Key Steps
The carry identity must be checked carefully. From
$$an_i+c_i=d_i+10c_{i+1},$$
summing gives
$$aS(N)+\sum c_i=S(aN)+10\sum c_{i+1}.$$
Because $c_0=0$, the two carry sums differ by exactly the final carry term. Omitting this bookkeeping produces an incorrect formula.
The estimate on carries uses
$$10c_{i+1}\le an_i+c_i.$$
After summation, the terms involving carries telescope. If one replaces $\sum c_i-\sum c_{i+1}$ by $0$, the argument loses the only information that survives the summation.
For the case $9\mid k$, the choice
$$N_m=\frac{10^m-1}{9}$$
is essential. Taking powers of $10$ would give $S(N)=1$ and would not force the ratio toward $0$.
Alternative Approaches
A different approach starts from the representation
$$S(X)=X-9\sum_j t_j,$$
where the integers $t_j$ count all decimal carry operations needed to reduce $X$ to its digit sum. One can express the digit sum after multiplication entirely in terms of carry counts and derive the optimal constant through a combinatorial analysis of carries. This approach stays within elementary decimal arithmetic but requires more bookkeeping.
Another method uses the congruence
$$S(X)\equiv X\pmod9$$
together with a study of the minimal positive representative of a residue class modulo $9$. Combined with carefully chosen repunits $N_m$, it yields both the existence criterion and the sharpness of the constant. The carry argument is preferable because it directly explains why the factor $9$ governs the problem and makes the extremal constant transparent.