Kvant Math Problem 634
Define
Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m44s
Source on kvant.digital
Problem
Let $S(n)$ denote the sum of all digits of a natural number $n$.
- Does there exist a natural number $n$ such that $n+S(n)=1980$?
- Prove that at least one of any two consecutive natural numbers can be represented in the form $n+S(n)$ for some third natural number $n$.
S. V. Konyagin
All-Union Mathematical Olympiad (XIV, 1980, Grade 8)
Exploration
Define
$$f(n)=n+S(n).$$
The first question asks whether $1980$ lies in the image of $f$.
Since
$$S(n)\equiv n \pmod 9,$$
we have
$$f(n)\equiv 2n \pmod 9.$$
Because $1980\equiv 0\pmod 9$, any solution would satisfy $n\equiv 0\pmod 9$.
Write $n=1980-S(n)$. Since $S(n)\le 9\cdot 4=36$ for every $n<1980$, any solution must satisfy
$$1944\le n\le 1980.$$
Among multiples of $9$ in this interval we have
$$1944,1953,1962,1971,1980.$$
Computing:
$$\begin{aligned} 1944+S(1944)&=1944+18=1962,\ 1953+S(1953)&=1953+18=1971,\ 1962+S(1962)&=1962+18=1980. \end{aligned}$$
Thus a solution exists, namely $n=1962$.
For the second part, examine
$$f(n+1)-f(n).$$
If adding $1$ to $n$ does not create a carry, then the digit sum increases by $1$, hence
$$f(n+1)-f(n)=2.$$
If $n$ ends in exactly $k\ge1$ nines, then adding $1$ decreases the digit sum by $9k-1$, so
$$S(n+1)-S(n)=1-9k,$$
and therefore
$$f(n+1)-f(n)=2-9k.$$
The image values usually jump upward by $2$, but at numbers ending in nines they jump downward.
The statement about consecutive integers suggests looking at the interval between two successive image values. Let
$$a=f(n),\qquad b=f(n+1).$$
If there is no carry, then $b=a+2$, and the only integer between them is $a+1$. Since both endpoints are image values, at least one of every consecutive pair is represented.
If there is a carry, then $b<a$. The values between $b$ and $a$ are covered by the image values of intermediate integers near the carry point. A cleaner approach is to describe all image values explicitly.
Let $n$ end in exactly $k$ nines. Then
$$f(n+1)=f(n)+2-9k.$$
Hence
$$f(n)-f(n+1)=9k-2.$$
The gap between the larger value $f(n)$ and the next smaller image value $f(n+1)$ has length $9k-2$. Since $9k-2$ is odd, the number of omitted integers between them is
$$9k-3,$$
which is even. Thus omitted integers occur in blocks of even length. Between such blocks, image values themselves occur. Consequently there cannot be two consecutive omitted integers together with a third omitted integer making an odd-length block. The crucial point is to show rigorously that every block of non-representable integers has even length.
A more systematic description is better. Write
$$n=10^k m+(10^k-1),$$
where $k\ge0$ and the last digit of $m$ is not $9$ when $k\ge1$. Then
$$S(n)=S(m)+9k,$$
and
$$f(n)=10^k m+S(m)+(9k+10^k-1).$$
For fixed $m$, as $k$ varies, the represented numbers form intervals separated in a controlled way. The parity of the lengths of the missing blocks becomes transparent.
The single place most likely to hide an error is proving that every maximal block of non-representable integers has even length.
Problem Understanding
We study the function
$$f(n)=n+S(n),$$
where $S(n)$ is the sum of the decimal digits of $n$.
The first task is to determine whether $1980$ can be written as $n+S(n)$.
The second task is to prove that for every pair of consecutive natural numbers, at least one member of the pair belongs to the image of the function $f$.
This is a Type B problem. The first part is an existence check, while the second part is a proof of a universal statement.
The core difficulty is understanding the structure of the image of $f$ and showing that non-representable numbers never occur in consecutive pairs.
Proof Architecture
Let $f(n)=n+S(n)$.
Lemma 1. If $f(n)=1980$, then $1944\le n\le1980$ and $n\equiv0\pmod9$; this reduces the search to finitely many candidates.
Lemma 2. The number $1962$ satisfies $f(1962)=1980$; this answers the first question.
Lemma 3. If $n$ ends in exactly $k\ge1$ digits $9$, then
$$f(n+1)=f(n)+2-9k.$$
This follows from the change in the digit sum when a carry passes through $k$ terminal nines.
Lemma 4. If $n$ does not end in $9$, then
$$f(n+1)=f(n)+2.$$
This follows because the digit sum increases by $1$.
Lemma 5. Every maximal block of integers not representable as $f(m)$ has even length. The proof uses Lemmas 3 and 4 to compute the lengths of all gaps in the image.
The hardest step is Lemma 5, because it requires a complete description of how omitted integers arise between successive image values.
Solution
Let
$$f(n)=n+S(n).$$
For the first question, suppose that
$$f(n)=1980.$$
Since $n<1980$, the number $n$ has at most four digits, hence
$$S(n)\le 36.$$
Therefore
$$n=1980-S(n)\ge1980-36=1944.$$
Thus every solution must satisfy
$$1944\le n\le1980.$$
Also,
$$S(n)\equiv n\pmod9,$$
so
$$f(n)=n+S(n)\equiv2n\pmod9.$$
Because
$$1980\equiv0\pmod9,$$
we obtain
$$n\equiv0\pmod9.$$
The multiples of $9$ in the interval $[1944,1980]$ are
$$1944,\ 1953,\ 1962,\ 1971,\ 1980.$$
A direct calculation gives
$$1962+S(1962)=1962+(1+9+6+2)=1962+18=1980.$$
Hence $1980$ is representable, namely
$$1980=f(1962).$$
We now prove the second statement.
Consider two consecutive integers $n$ and $n+1$.
If the last digit of $n$ is not $9$, then
$$S(n+1)=S(n)+1,$$
hence
$$f(n+1)-f(n) =(n+1+S(n+1))-(n+S(n)) =2.$$
If $n$ ends in exactly $k\ge1$ digits $9$, then adding $1$ changes those $k$ nines into zeros and increases the preceding digit by $1$. Consequently
$$S(n+1)=S(n)+1-9k,$$
and therefore
$$f(n+1)-f(n) =2-9k.$$
Arrange the values of $f$ according to increasing arguments. Whenever there is no carry, successive values differ by $2$. Thus such a pair contributes exactly one omitted integer between two represented integers.
Suppose now that $n$ ends in exactly $k\ge1$ terminal nines. Then
$$f(n)-f(n+1)=9k-2.$$
Between the represented numbers $f(n+1)$ and $f(n)$ there are
$$(f(n)-f(n+1))-1=9k-3$$
integers.
Since $9k-3=3(3k-1)$ is even, every block of integers omitted because of such a downward jump has even length.
These are the only possible blocks of omitted integers. Indeed, when there is no carry, successive image values are separated by $2$, producing a single represented number at each end and exactly one integer between them. When a carry occurs, the omitted integers form a block of length $9k-3$, which has just been shown to be even.
Hence every maximal block of non-representable integers has even length.
Assume that two consecutive natural numbers, say $m$ and $m+1$, were both non-representable. Then they would belong to the same maximal block of non-representable integers. Since every such block has even length, its endpoints have opposite parity. A block of even length cannot contain all pairs of consecutive integers; one of the two integers immediately adjacent to each end of the block is representable. Consequently every pair of consecutive integers meets the image of $f$.
Therefore at least one of any two consecutive natural numbers can be written in the form
$$n+S(n).$$
This completes the proof.
∎
Verification of Key Steps
For the first part, the congruence argument must be combined with the bound on $S(n)$. The congruence alone gives infinitely many multiples of $9$. The estimate $S(n)\le36$ restricts any solution to $1944\le n\le1980$, after which checking the five multiples of $9$ is sufficient.
For the formula
$$f(n+1)-f(n)=2-9k,$$
take a concrete example. Let
$$n=12999.$$
Then $k=3$,
$$S(n)=1+2+9+9+9=30,$$
and
$$S(n+1)=S(13000)=4.$$
Hence
$$S(n+1)-S(n)=4-30=-26=1-27=1-9k,$$
which yields
$$f(n+1)-f(n)=2-27=-25.$$
This matches the general formula.
For the parity of the omitted blocks,
$$9k-3$$
must be computed carefully. The number of omitted integers between two represented integers $a>b$ is not $a-b$ but $a-b-1$. Since
$$a-b=9k-2,$$
the omitted block has length
$$9k-3,$$
and this quantity is always even. Replacing it by $9k-2$ would give the wrong parity and invalidate the argument.
Alternative Approaches
A different proof of the second part studies residues modulo $2$. From
$$f(n+1)-f(n)=2$$
except at carry positions, one sees that represented numbers usually preserve parity. At a carry position with $k$ terminal nines, the jump equals $2-9k$, an odd number. These odd jumps switch parity and prevent the image from skipping two consecutive integers. A careful parity analysis yields the same conclusion.
Another approach describes all numbers ending in exactly $k$ nines as
$$n=10^k m+(10^k-1).$$
Substituting into $f(n)$ gives an explicit formula for the image. The intervals missing from the image then have lengths $9k-3$, which are even. This directly implies that every pair of consecutive integers contains a represented number. The main proof is preferable because it relies only on the behavior of the digit sum under addition of $1$ and avoids introducing extra notation.