Kvant Math Problem 614

Let $s(n)$ denote the sum of the digits of the single number $n$.

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 2m04s
Source on kvant.digital

Problem

For each natural number $n$, let $S(n)$ denote the sum of the digits of all natural numbers from 1 to $n$ (in decimal notation): $$\begin{gather*} S(1)=1,\quad S(2)=3,\quad S(3)=6,\quad \ldots,\quad S(9)=45,\ S(10)=46,\quad S(11)=48,\quad S(12)=51,\quad \ldots \end{gather*}$$

  1. Find $S(100)$.
  2. Prove that $S(10^k-1)=45k\cdot10^{k-1}$ for all $k=1$, 2, $\ldots$
  3. Prove that for any two-digit number $\overline{ab}$, $$S(\overline{ab})=5a^2+ab+41a+\dfrac{b(b+1)}{2}.$$
  4. Find a similar formula for three-digit numbers.
  1. Compute $S(1980)$.

Andrzej Paszewicz (Poland)

Exploration

Let $s(n)$ denote the sum of the digits of the single number $n$. Then

$$S(n)=\sum_{m=1}^{n}s(m).$$

The first task is to understand how digit sums are distributed among all numbers with a fixed number of digits.

For $1,\dots,9$,

$$S(9)=1+2+\cdots+9=45.$$

For $0,\dots,99$, each digit $0,1,\dots,9$ appears equally often in the units place, namely $10$ times. Hence the contribution of the units digit is

$$10(0+1+\cdots+9)=450.$$

The same is true for the tens digit. Thus the total digit sum of all numbers from $0$ to $99$ equals $900$. Since the number $0$ contributes nothing,

$$S(99)=900.$$

This suggests

$$S(10^k-1)=45k,10^{k-1}.$$

The crucial point is to justify the equal distribution of digits in every position among the numbers $0,\dots,10^k-1$.

For a two-digit number $10a+b$, it is natural to split the interval $1,\dots,10a+b$ into the complete blocks

$$0,\dots,9;\quad 10,\dots,19;\quad \ldots;\quad 10(a-1),\dots,10(a-1)+9,$$

and the final partial block

$$10a,\dots,10a+b.$$

Computing the contribution of each block should produce the required quadratic formula.

For three-digit numbers, the same decomposition into complete hundreds and a final partial hundred should lead to a cubic polynomial in the hundreds digit together with a term involving the last two digits.

Finally, to find $S(1980)$, write

$$1980=1000+980$$

and use the three-digit formula for $980$ together with the contribution of the leading digit $1$ in the numbers $1000,\dots,1980$.

Problem Understanding

We are given

$$S(n)=\sum_{m=1}^{n}s(m),$$

where $s(m)$ is the sum of the decimal digits of $m$.

The problem asks for explicit evaluations of $S(100)$ and $S(1980)$, a proof of the general formula

$$S(10^k-1)=45k,10^{k-1},$$

a derivation of a formula for a two-digit number $10a+b$, and an analogous formula for a three-digit number.

This is a Type B problem. The main task is to establish exact formulas.

The core difficulty is counting digit contributions position by position and handling the incomplete final block when the upper bound is not of the form $10^k-1$.

Proof Architecture

Lemma 1. For every $k\ge1$,

$$S(10^k-1)=45k,10^{k-1}.$$

Among the numbers $0,\dots,10^k-1$, each digit appears exactly $10^{k-1}$ times in every position.

Lemma 2. For a two-digit number $10a+b$,

$$S(10a+b)=5a^2+ab+41a+\frac{b(b+1)}2.$$

Split the interval into $a$ complete blocks of length $10$ and one partial block.

Lemma 3. If

$$n=100a+r,\qquad 0\le r\le99,$$

then

$$S(n)=4500\frac{a(a-1)}2+100a+100S(a-1)+a(r+1)+S(r).$$

Sum the contributions of complete hundreds and the last partial hundred.

Lemma 4. Substituting the two-digit formula for $S(r)$ yields an explicit formula for every three-digit number.

The most delicate step is Lemma 1, because the entire argument depends on counting the occurrences of each digit correctly.

Solution

For every integer $m\ge0$, let $s(m)$ be the sum of the decimal digits of $m$. Then

$$S(n)=\sum_{m=1}^{n}s(m).$$

We first prove the formula for numbers of the form $10^k-1$.

Consider all integers from $0$ to $10^k-1$. Write them with exactly $k$ digits, allowing leading zeros. Fix one digit position. For each choice of the remaining $k-1$ positions there are exactly ten possibilities for the chosen position, namely $0,1,\dots,9$. Hence each digit occurs exactly $10^{k-1}$ times in that position.

The sum of the digits appearing in that position is therefore

$$10^{k-1}(0+1+\cdots+9) =45\cdot10^{k-1}.$$

There are $k$ positions, so the sum of all digit sums of the numbers from $0$ to $10^k-1$ equals

$$45k,10^{k-1}.$$

Since the number $0$ contributes $0$, we obtain

$$S(10^k-1)=45k,10^{k-1}.$$

This proves part 2.

For $k=2$,

$$S(99)=45\cdot2\cdot10=900.$$

Since

$$S(100)=S(99)+s(100)=900+1,$$

we get

$$S(100)=901.$$

This answers part 1.

Now let $n=10a+b$, where $1\le a\le9$ and $0\le b\le9$.

The numbers from $0$ to $10a+b$ consist of the $a$ complete blocks

$$10t,\dots,10t+9, \qquad t=0,\dots,a-1,$$

and the partial block

$$10a,\dots,10a+b.$$

For a complete block with fixed $t$,

$$s(10t+i)=t+i, \qquad i=0,\dots,9.$$

Therefore the total contribution of that block is

$$10t+(0+1+\cdots+9)=10t+45.$$

Summing over all complete blocks,

$$\sum_{t=0}^{a-1}(10t+45) =10\frac{a(a-1)}2+45a =5a^2+40a.$$

For the final block,

$$\sum_{i=0}^{b}(a+i) =(b+1)a+\frac{b(b+1)}2.$$

Adding these contributions gives

$$S(10a+b) =5a^2+40a+(b+1)a+\frac{b(b+1)}2.$$

Hence

$$S(10a+b) =5a^2+ab+41a+\frac{b(b+1)}2.$$

This proves part 3.

For a three-digit number

$$n=100a+10b+c,$$

put

$$r=10b+c.$$

The numbers from $0$ to $100a+r$ consist of the complete hundreds

$$100t,\dots,100t+99, \qquad t=0,\dots,a-1,$$

and the final partial hundred

$$100a,\dots,100a+r.$$

For fixed $t$ and $0\le u\le99$,

$$s(100t+u)=t+s(u).$$

Thus the total contribution of the hundred block indexed by $t$ is

$$100t+\sum_{u=0}^{99}s(u) =100t+S(99) =100t+900.$$

Summing over $t=0,\dots,a-1$,

$$\sum_{t=0}^{a-1}(100t+900) =50a(a-1)+900a.$$

The final partial hundred contributes

$$(r+1)a+S(r).$$

Consequently,

$$S(100a+r) =50a(a-1)+900a+(r+1)a+S(r).$$

Substituting

$$r=10b+c$$

and the already proved formula

$$S(r) =5b^2+bc+41b+\frac{c(c+1)}2,$$

we obtain

$$\begin{aligned} S(100a+10b+c) &=50a(a-1)+900a+(10b+c+1)a \ &\qquad +5b^2+bc+41b+\frac{c(c+1)}2. \end{aligned}$$

After collecting terms,

$$S(100a+10b+c) = 50a^2+851a+10ab+ac +5b^2+bc+41b+\frac{c(c+1)}2.$$

This is the required analogue for three-digit numbers.

Finally, to compute $S(1980)$, write

$$1980=1000+980.$$

The numbers from $1000$ to $1980$ have leading digit $1$, contributing

$$981.$$

The remaining three digits run through all numbers from $0$ to $980$, contributing $S(980)$. Hence

$$S(1980)=S(999)+981+S(980).$$

Using

$$S(999)=45\cdot3\cdot100=13500,$$

and the three-digit formula with

$$a=9,\quad b=8,\quad c=0,$$

we get

$$S(980) = 50\cdot81+851\cdot9+10\cdot9\cdot8 +5\cdot64+41\cdot8.$$

Thus

$$S(980)=4050+7659+720+320+328=13077.$$

Therefore

$$S(1980)=13500+981+13077=27558.$$

This completes the proof.

∎

Verification of Key Steps

For Lemma 1, fix a position among the $k$ decimal places. There are $10^{k-1}$ choices for the remaining positions. For each such choice, the chosen digit takes each value from $0$ to $9$ exactly once. Hence every digit occurs exactly $10^{k-1}$ times. A common mistake is to forget leading zeros, which destroys the symmetry.

For the two-digit formula, test $a=1$, $b=0$. The formula gives

$$5+0+41=46.$$

Directly,

$$S(10)=S(9)+1=45+1=46.$$

The block decomposition is therefore consistent at the first nontrivial case.

For $S(1980)$, verify the decomposition independently. The interval $1000,\dots,1980$ contains

$$1980-1000+1=981$$

numbers. Each contributes $1$ from the thousands digit. After removing that digit, the remaining parts are exactly the numbers $0,\dots,980$. Hence the contribution is $981+S(980)$, not $980+S(980)$. Missing the endpoint count would produce an incorrect answer.

Alternative Approaches

The formula for $S(10^k-1)$ can also be proved by induction. Assume

$$S(10^k-1)=45k,10^{k-1}.$$

The interval from $0$ to $10^{k+1}-1$ splits into ten blocks of length $10^k$. The lower $k$ digits contribute $10S(10^k-1)$, while the leading digit contributes

$$10^k(0+1+\cdots+9)=45\cdot10^k.$$

This yields the same formula for $k+1$.

For the formulas involving two-digit and three-digit numbers, one may derive a general recursion. If

$$n=10q+r,\qquad 0\le r\le9,$$

then

$$S(n)=10S(q-1)+45q+(r+1)q+\frac{r(r+1)}2.$$

Applying this recursion once gives the two-digit formula, and applying it twice gives the three-digit formula. The direct block-counting method used above is preferable because every contribution is visible immediately and no auxiliary recurrence is required.