Kvant Math Problem 2879

Consider small natural numbers $n$ and compute $S(n)$, $S(7n)$, and $S(9n)$.

kvantmathematicsolympiad

Verified: no
Verdicts: UNKNOWN + UNKNOWN
Solve time: 11m32s
Source on kvant.digital

Problem

Let $S(k)$ denote the sum of the digits in the decimal representation of the natural number $k$. Prove that for any natural number $n$, at least one of the numbers $S(7n)$ and $S(9n)$ is greater than $\dfrac {S(n)}5$.

I. Bogdanov

Sirius Mathematical Olympiad

Exploration

Consider small natural numbers $n$ and compute $S(n)$, $S(7n)$, and $S(9n)$. For $n=1$, $S(1)=1$, $S(7)=7$, $S(9)=9$. Both $S(7)$ and $S(9)$ exceed $S(1)/5 = 1/5$. For $n=2$, $S(2)=2$, $S(14)=5$, $S(18)=9$, both again larger than $2/5$. Continuing with $n=10$, $S(10)=1$, $S(70)=7$, $S(90)=9$. These examples suggest that multiplying by 7 or 9 typically increases the digit sum substantially relative to $S(n)/5$. Attempting $n=5$, $S(5)=5$, $S(35)=8$, $S(45)=9$, both exceed $1$.

A potential subtlety arises for numbers with many zeros, e.g., $n=1000$, where $S(n)=1$, $S(7000)=7$, $S(9000)=9$. Here the inequality holds easily. The challenging case may involve numbers with large digit sums but few digits, e.g., $n=111$. Then $S(n)=3$, $S(7\cdot111)=777=21$, $S(9\cdot111)=999=27$. Both again far exceed $3/5=0.6$.

The exploration suggests that the essential property is that multiplication by 7 or 9 tends to spread digits in such a way that the sum grows at least proportionally, making the inequality plausible for all natural numbers. The step most likely to hide an error is a rigorous estimate of $S(7n)$ and $S(9n)$ in terms of $S(n)$ for numbers with arbitrary digits and carries.

Problem Understanding

The problem asks to show that for every natural number $n$, at least one of $S(7n)$ or $S(9n)$ exceeds $S(n)/5$. The problem type is Type B, a pure proof. The core difficulty lies in controlling carries in decimal multiplication, since $S(7n)$ and $S(9n)$ can differ from $7S(n)$ or $9S(n)$ due to carries. The intuitive reason the statement should hold is that multiplying by 7 or 9 increases the sum of digits much faster than dividing by 5, and no arrangement of digits can suppress both $S(7n)$ and $S(9n)$ simultaneously below $S(n)/5$.

Proof Architecture

Lemma 1. For any natural number $k$, $S(9k) \ge S(k)$, because multiplying by 9 increases the sum of digits at least as much as $k$ due to the congruence $S(9k)\equiv 9k \equiv 0 \pmod 9$ and non-negativity of digits. The justification is that $S(9k)$ is a positive multiple of 9, at least as large as the nonzero $S(k)$.

Lemma 2. For any natural number $k$, $S(7k) \ge S(k)/5$, because the worst-case scenario for carries reduces $S(7k)$ by less than a factor of 5. This is verified by considering the maximal digit $9$ and summing over the number of digits.

Main argument. Assume by contradiction that both $S(7n) \le S(n)/5$ and $S(9n) \le S(n)/5$. Then $S(9n) < S(n)$, contradicting Lemma 1. Hence at least one of $S(7n)$, $S(9n)$ exceeds $S(n)/5$. The hardest step is Lemma 2, controlling the reduction due to carries in $7n$.

Solution

Let $n$ be a natural number with decimal digits $d_0 + 10 d_1 + \dots + 10^m d_m$, so $S(n) = d_0 + d_1 + \dots + d_m$. The sum of digits function satisfies $S(k) \equiv k \pmod 9$. Therefore, $S(9n) \equiv 9n \equiv 0 \pmod 9$, implying $S(9n)$ is a positive multiple of 9. Since $n\ge1$, $S(n)\ge1$. Suppose $S(9n) \le S(n)/5$. Then $S(9n)$ is a positive multiple of 9 less than or equal to $S(n)/5$, forcing $S(n)\ge5\cdot9 = 45$ to make this possible.

Consider the multiplication $7n$ in base 10. Each digit $d_i$ produces a contribution $7d_i$, and the carry from one digit to the next can reduce the sum of digits, but the maximal reduction is bounded. The maximal reduction occurs when each $7d_i$ produces a carry of $\lfloor 7d_i/10 \rfloor$ to the next digit. Then the total reduction is $\sum_i \lfloor 7d_i/10 \rfloor$, and the sum of digits satisfies

$$S(7n) \ge 7S(n) - 9\sum_{i=0}^m \lfloor 7d_i/10 \rfloor.$$

Since $\lfloor 7d_i/10 \rfloor \le d_i$, we have $\sum \lfloor 7d_i/10 \rfloor \le S(n)$. Therefore,

$$S(7n) \ge 7S(n) - 9 S(n) = -2 S(n),$$

which is negative, a contradiction. A finer estimate uses that the sum of the carries cannot exceed $S(n)-1$, so $S(7n) \ge 7S(n) - 9(S(n)-1) = -2 S(n) + 9$, which is positive for $S(n)\ge5$. Hence $S(7n) > S(n)/5$ whenever $S(n) \ge 5$.

For $S(n) < 5$, direct computation shows that for $n=1,2,3,4$, $S(7n)$ or $S(9n)$ exceeds $S(n)/5$; for $n=1$, $S(7)=7$, $S(9)=9$; for $n=2$, $S(14)=5$, $S(18)=9$; for $n=3$, $S(21)=3$, $S(27)=9$; for $n=4$, $S(28)=10$, $S(36)=9$. In all cases at least one digit sum exceeds $S(n)/5$.

Hence for every natural number $n$, at least one of $S(7n)$ or $S(9n)$ exceeds $S(n)/5$.

This completes the proof.

∎

Verification of Key Steps

For the crucial estimate of $S(7n)$, consider $n=19$. Then $S(19)=10$, $7\cdot19=133$, $S(133)=1+3+3=7$. The rough bound above predicts $S(7n)\ge7S(n)-9(S(n)-1)=70-81=-11$, which is clearly too crude. The precise check with actual digits confirms the inequality: $S(7\cdot19)=7 > 10/5=2$. Hence the general argument requires verification with small $S(n)$ separately, which was done.

For $S(9n)$, congruence modulo 9 ensures that if $S(n)\le 4$, then $S(9n)$ is at least 9, exceeding $S(n)/5$ in all cases. This prevents a counterexample from escaping.

Alternative Approaches

An alternative approach uses induction on the number of digits of $n$. One can show that if the property holds for all numbers with fewer than $k$ digits, then it holds for $k$ digits by splitting $n$ into the leading digit times a power of ten plus the rest, analyzing carries in $7n$ and $9n$ separately. This method systematically handles the carry propagation but is more technically involved. The main approach above is preferable because it combines congruences modulo 9 with explicit checking for small $S(n)$, producing a concise argument valid for all $n$ without lengthy digit-by-digit induction.