Kvant Math Problem 127

Verified: no
Verdicts: SKIP + SKIP
Solve time: 8m57s
Source on kvant.digital

Problem

For each natural number $n$, let $s(n)$ denote the sum of its digits (in decimal notation). Call a natural number $m$ special if it cannot be represented in the form $m=n+s(n)$, where $n$ is some natural number. (For example, the number $117$ is not special, since $117= 108+s(108)=108+9$, while the number $121$ is, as is easy to verify, special.) Is it true that there are only finitely many special numbers?

Exploration

Computing the first few values of $m = n + s(n)$ quickly shows that many numbers can be represented in this form. For example, $1 = 0 + s(0)$, $2 = 1 + s(1)$, and so on. Special numbers, by definition, are gaps in the sequence of numbers of the form $n + s(n)$. Small numbers such as $121$ appear to be special, but larger numbers seem less likely to be special because the function $n + s(n)$ grows roughly linearly with $n$, and $s(n)$ grows much slower than $n$.

Testing small cases, for $n$ up to 100, one sees that gaps like 1, 2, or 3 units exist, but the gaps never grow arbitrarily large. This suggests that beyond some threshold, every large number can be written as $n + s(n)$. The core difficulty is to rigorously argue that no large number can be special, rather than just observing it experimentally. The likely critical step is quantifying the size of $s(n)$ relative to $n$ to show that for $m$ large enough, the interval $[m - 9k, m]$ always contains an $n$ satisfying $m = n + s(n)$, where $k$ is the number of digits of $m$.

Problem Understanding

The problem asks to classify all natural numbers that cannot be written as $m = n + s(n)$. This is a Type A problem: "Find all $m$ that are special." The core difficulty is proving finiteness rigorously. Intuitively, since $s(n)$ grows much slower than $n$, for sufficiently large $m$, subtracting the maximum possible digit sum produces an $n$ that works. Hence the set of special numbers should be finite, as only small $m$ can fail this representation.

Proof Architecture

Lemma 1. For any natural number $n$ with $k$ digits, $s(n) \le 9k$. This follows from the definition of the decimal digit sum.

Lemma 2. Any natural number $m > 9k + 10^{k-1}$ can be represented as $m = n + s(n)$ for some $n$ with $k$ digits. This is justified by considering $n = m - t$ with $t \le 9k$, so $s(n) = t$ can always be achieved by choosing $n$ near $m - 9k$.

Lemma 3. Since $k = \lfloor \log_{10} m \rfloor + 1$, for sufficiently large $m$, $9k < m - 10^{k-1}$, which ensures Lemma 2 applies. The critical step is showing that the interval $[m - 9k, m - 1]$ contains a number $n$ with $s(n) = m - n$.

The hardest part is Lemma 2, since it requires constructing an $n$ with a prescribed digit sum. The core insight is that for large numbers, small adjustments in digits can realize any $t \le 9k$ as $s(n)$.

Solution

For any natural number $n$ with $k$ digits, the sum of its digits satisfies $s(n) \le 9k$. Let $m$ be a natural number, and suppose $m > 9k + 10^{k-1}$, where $k$ is the number of digits in $m$. Consider the numbers $n$ in the interval $[m - 9k, m - 1]$. Each $n$ in this interval has at most $k$ digits, and thus $s(n) \le 9k$. Define $t = m - n$. Then $1 \le t \le 9k$. The task is to find $n$ such that $s(n) = t$.

To see that such an $n$ exists, note that any number with $k$ digits can realize any digit sum $t$ from $1$ up to $9k$ by adjusting its digits. Specifically, start from $m - 9k$ and increment by one, modifying the digits to ensure the sum of digits equals $t = m - n$. This process is always possible because $m - 9k \ge 10^{k-1}$, so we have sufficient flexibility in the digits to realize any $t$ up to $9k$. Setting $n = m - t$ with this digit sum produces $m = n + s(n)$.

Since the construction works for all $m$ exceeding a certain bound, only numbers smaller than this bound can be special. Therefore the set of special numbers is finite. This completes the proof.

∎

Verification of Key Steps

The key delicate step is constructing $n$ with $s(n) = t$ for $t \le 9k$. To verify this independently, consider that the smallest $k$-digit number is $10^{k-1}$, which has a digit sum of $1$. Incrementing units digits or redistributing digits can reach any sum $t \le 9k$, as the maximum sum for $k$ digits is $9k$. For example, for $k = 3$, the interval $[100, m - 1]$ allows sums from $1$ to $27$, covering all required $t$ for $m$ in the relevant range. Any miscounting of digits or off-by-one errors would occur only if $m - 9k < 10^{k-1}$, but the bound $m > 9k + 10^{k-1}$ prevents this.

The second verification is that the interval $[m - 9k, m - 1]$ always contains numbers with exactly $k$ digits. For $m$ large enough, $m - 9k \ge 10^{k-1}$, ensuring all $n$ constructed have $k$ digits. Exhaustively checking small $k$ shows that any $t$ can indeed be realized as a digit sum.

Alternative Approaches

One alternative is to use a direct combinatorial argument counting the number of numbers representable as $n + s(n)$ for each $k$. The number of $k$-digit $n$ is $9 \cdot 10^{k-1}$, and the maximum digit sum is $9k$, so the representable numbers occupy intervals of length $9k$ repeated over $10^{k-1}$ numbers. For sufficiently large $k$, these intervals cover all numbers beyond a threshold, establishing finiteness. The main approach is preferable because it directly constructs the $n$ corresponding to $m$, giving a more explicit and rigorous proof rather than relying on counting heuristics.