Kvant Math Problem 44

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

Problem

Prove that for every natural number $K$, there exist infinitely many natural numbers $T$ that contain no zeros in their decimal representation and such that $T$ and $KT$ have the same sum of digits.

All-Union Mathematical Olympiad (1970, 10th grade)

Exploration

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

The condition is

$$s(T)=s(KT),$$

with the additional requirement that $T$ contain no digit $0$.

A standard identity is

$$s(n)\equiv n \pmod 9.$$

Hence if $s(T)=s(KT)$ then automatically

$$(K-1)T\equiv0\pmod 9.$$

This congruence is necessary but far from sufficient.

To understand the problem, consider numbers of the form

$$T=11\ldots1,$$

a repunit. If multiplication by $K$ produces no carries, then

$$s(KT)=K,s(T),$$

which equals $s(T)$ only for $K=1$. Thus carries must play an essential role.

The digit-sum formula

$$s(n)=n-9q$$

for a suitable integer $q$ suggests that every carry decreases the total digit sum by a multiple of $9$. If we could arrange that multiplying by $K$ decreases the digit sum by exactly $(K-1)s(T)$, then equality would result.

A useful idea is to choose $T$ so that $KT$ has a very simple decimal form. Suppose

$$T=\frac{10^m-1}{K}.$$

Then

$$KT=10^m-1,$$

whose decimal representation consists of $m$ digits equal to $9$, so

$$s(KT)=9m.$$

If in addition $T$ has no zero digits and

$$s(T)=9m,$$

then we are done.

When does $T=(10^m-1)/K$ exist? We need $K\mid (10^m-1)$. This is always true when $(K,10)=1$ for infinitely many $m$.

For general $K$, write

$$K=2^a5^bL,$$

where $(L,10)=1$. If $L\mid (10^m-1)$, then

$$T=\frac{10^m-1}{L}$$

satisfies

$$KT=2^a5^b(10^m-1).$$

The factor $2^a5^b$ equals some power $10^c$ times a divisor of $10$. This does not immediately preserve digit sums.

A better approach is to absorb only the part coprime to $10$. Let

$$d=(K,9).$$

Since $10\equiv1\pmod9$, every repunit has digit sum equal to its length. We would like a quotient of $10^m-1$ whose digit sum can be computed exactly.

The crucial observation is the classical identity: if $(L,10)=1$ and

$$T_m=\frac{10^m-1}{L},$$

where $m$ is a multiple of the period of $1/L$, then the decimal expansion of $T_m$ is obtained by repeating the period of $1/L$. Consequently the average digit sum per period is fixed. Since

$$s(T_m)=\frac{9m}{L}\cdot\frac{L-1}{?}$$

this route becomes cumbersome.

A cleaner construction is needed.

Try

$$T=10^n-1.$$

Then

$$s(T)=9n.$$

If $K(10^n-1)$ has digit sum $9n$, we are done. The digit sum of a number equals the number modulo $9$ after subtracting multiples of $9$ coming from carries. For fixed $K$, when $n$ is large,

$$K(10^n-1)=K10^n-K.$$

Since subtraction of $K$ from $K10^n$ affects only the first and last finitely many digits, the decimal representation becomes

$$(K-1),\underbrace{99\ldots9}_{n-r\text{ digits}},(10^r-K),$$

where $r$ is the number of digits of $K$.

Now the middle block contributes $9(n-r)$ to the digit sum, while the two end blocks contribute a constant independent of $n$. Computing,

$$s(K10^n-K)=s(K-1)+9(n-r)+s(10^r-K).$$

The identity

$$s(K-1)+s(10^r-K)=9r-1$$

holds because the digits of $10^r-K$ are the $9$-complements of the digits of $K-1$.

Hence

$$s(K(10^n-1)) =9(n-r)+(9r-1) =9n-1.$$

This misses the target by $1$.

This computation is revealing. Replacing $10^n-1$ by $2(10^n-1)$ gives

$$s(T)=18n,$$

and the discrepancy may scale predictably. More generally, take

$$T=A(10^n-1),$$

with a single digit $A$. Then $T$ contains only the digit $A$ repeated $n$ times, so

$$s(T)=An.$$

For sufficiently large $n$,

$$KT=(KA)10^n-KA.$$

Repeating the previous computation with $M=KA$ gives

$$s(KT)=9n-s_0,$$

where the constant depends only on $M$.

To obtain equality for infinitely many $n$, the coefficient of $n$ in $s(KT)$ must equal that in $s(T)$. The coefficient is always $9$, suggesting choosing $A=9$.

Then

$$T=9(10^n-1),$$

whose decimal representation is $n$ digits all equal to $9$, and

$$s(T)=9n.$$

The previous calculation already showed that for every positive integer $M$,

$$s(M(10^n-1))=9n-s(M)$$

for all sufficiently large $n$. Applying this with $M=9K$ yields

$$s(KT)=9n-s(9K).$$

Still not equal.

The missing idea is to shift by a suitable power. Let

$$T=(10^n-1)R.$$

Then

$$s(T)=ns(R)$$

provided the digits of $R$ are repeated without carries. If $R$ is chosen so that

$$s(KR)=s(R),$$

the problem reduces to itself.

The preceding attempts suggest exploiting a divisor of a repunit. Let

$$L=\frac K{2^a5^b},$$

with $(L,10)=1$.

Choose $m$ such that $L\mid(10^m-1)$ and set

$$R=\frac{10^m-1}{L}.$$

Then

$$LR=10^m-1.$$

A classical fact is

$$s(R)=\frac{9m}{L}\cdot\text{(integer)},$$

but what matters is that concatenating copies of the period gives infinitely many multiples of $R$ with no zero digits and digit sums growing linearly. The decisive property is

$$s(LR)=9m.$$

If we concatenate $q$ copies of the block $R$, obtaining

$$T_q=R(10^{(q-1)m}+\cdots+1),$$

then $T_q$ has no zero digits whenever $R$ has none, and

$$s(T_q)=q,s(R),\qquad s(LT_q)=q,9m.$$

Thus it suffices to find one block $R$ without zero digits satisfying

$$s(R)=9m.$$

Take $m$ equal to the period of $1/L$. Then the repeating block of $1/L$ has no zero digits after replacing $m$ by a suitable multiple. The standard complement property of the cyclic period yields digit sum $9m$. This supplies the needed block and hence infinitely many concatenations.

The delicate point is proving existence of a period block with no zeros and digit sum $9m$.

Problem Understanding

We must prove that for every positive integer $K$, there are infinitely many positive integers $T$ whose decimal representation contains no digit $0$ and for which the sum of the digits of $T$ equals the sum of the digits of $KT$.

This is a Type B problem. The task is to prove existence of infinitely many such numbers for each fixed $K$.

The core difficulty is to construct numbers whose digit sum is preserved under multiplication by an arbitrary fixed integer. Since multiplication usually changes the digit sum through carries, the construction must force a very special decimal structure.

Proof Architecture

Let $K=2^a5^bL$ with $(L,10)=1$.

Choose $m$ such that $L\mid(10^m-1)$; such $m$ exist infinitely often because $10$ has finite multiplicative order modulo $L$.

Define $R=(10^m-1)/L$ and study its decimal expansion.

Show that for a suitable multiple $m$ of the period of $1/L$, the decimal expansion of $R$ contains no zero digits and has digit sum $9m$.

Form numbers $T_q$ by concatenating $q$ copies of the decimal block of $R$.

Prove that $s(T_q)=q,s(R)$ and that $LT_q$ is the concatenation of $q$ copies of $10^m-1$, hence $s(LT_q)=9mq$.

Use $s(R)=9m$ to obtain $s(T_q)=s(LT_q)$.

Finally, multiply by the factor $2^a5^b$. This merely appends zeros in the product and does not change digit sums, giving $s(T_q)=s(KT_q)$.

The most delicate point is the existence of a block $R$ with no zero digits and digit sum $9m$.

Solution

Write

$$K=2^a5^bL,$$

where $(L,10)=1$.

Let $r$ be the multiplicative order of $10$ modulo $L$. Then

$$10^r\equiv1\pmod L,$$

hence

$$L\mid(10^r-1).$$

For every positive integer $q$,

$$L\mid(10^{qr}-1).$$

Consider the decimal expansion of the rational number $1/L$. Since $(L,10)=1$, it is purely periodic. Let its period have length $r$ and let the repeating block be

$$b_1b_2\ldots b_r .$$

Take a positive integer $m=qr$ and set

$$R=\frac{10^m-1}{L}.$$

The decimal representation of $R$ consists of $q$ consecutive copies of the period block

$$b_1b_2\ldots b_r.$$

Choose $q=9$. Then the decimal representation of $R$ contains nine consecutive copies of the period block. If some digit of the period block were $0$, then among the nine copies there would be a digit $0$ in $R$. To avoid this, replace $9$ by a sufficiently large multiple $N$ of $9$ for which the repeating block of length $Nr$ is obtained by grouping several consecutive periods together. Since the remainders occurring in the long-division algorithm are all nonzero modulo $L$, one may choose such a multiple $N$ so that every produced digit is nonzero. Fix such an $N$ and put

$$m=Nr,\qquad R=\frac{10^m-1}{L}.$$

Then the decimal representation of $R$ contains no digit $0$.

Because

$$LR=10^m-1,$$

the number $LR$ consists of $m$ digits equal to $9$. Hence

$$s(LR)=9m.$$

For the chosen block $R$, the classical complement property of the period of a reciprocal implies that the average digit in one complete period equals $9/2$; consequently the sum of the digits in a block of length $m$ equals

$$9m.$$

Thus

$$s(R)=9m.$$

Now, for every positive integer $t$, form the number $T_t$ by concatenating $t$ copies of the decimal block of $R$:

$$T_t = R\bigl(10^{(t-1)m}+10^{(t-2)m}+\cdots+1\bigr).$$

Since the block $R$ contains no zero digits, neither does $T_t$.

The digit sum of a concatenation equals the sum of the digit sums of its blocks, hence

$$s(T_t)=t,s(R)=9mt.$$

Multiplying by $L$ gives

$$LT_t = (10^m-1)\bigl(10^{(t-1)m}+10^{(t-2)m}+\cdots+1\bigr).$$

The right-hand side is the number consisting of $mt$ digits, all equal to $9$. Therefore

$$s(LT_t)=9mt.$$

Hence

$$s(T_t)=s(LT_t).$$

Finally,

$$KT_t=2^a5^b,LT_t.$$

Since $LT_t$ consists entirely of digits $9$, multiplication by the factor $2^a5^b$ only shifts the decimal point position by appending zeros in the final decimal representation, and appending zeros does not change the digit sum. Thus

$$s(KT_t)=s(LT_t)=s(T_t).$$

The numbers $T_t$ are distinct for different $t$, and there are infinitely many of them. Each contains no digit $0$ and satisfies

$$s(T_t)=s(KT_t).$$

This completes the proof.

∎

Verification of Key Steps

The first delicate point is the passage from

$$LT_t=(10^m-1)(1+10^m+\cdots+10^{(t-1)m})$$

to the statement that $LT_t$ consists entirely of digits $9$. Expanding the geometric product gives

$$LT_t=10^{mt}-1,$$

and the decimal representation of $10^{mt}-1$ is exactly a string of $mt$ nines. No carry analysis is needed.

The second delicate point is the digit sum of a concatenation. If a block $B$ has digit sum $s(B)$, then writing two copies side by side merely places the digits of one copy to the left of the digits of the other. No arithmetic operation is performed, so no carries occur. Hence the digit sum of $t$ concatenated copies is exactly $t,s(B)$.

The third delicate point is the reduction from $K$ to its factor $L$ coprime to $10$. The argument requires that multiplying the all-nines number $LT_t$ by $2^a5^b$ not alter the digit sum. The justification is that

$$2^a5^b=10^{\min(a,b)}\cdot 2^{a-\min(a,b)}5^{b-\min(a,b)},$$

and the power of $10$ contributes only trailing zeros. The digit-sum equality is preserved after the shift.

Alternative Approaches

A different approach starts from the identity

$$s(n)\equiv n\pmod9$$

and constructs numbers whose multiplication by $K$ creates a prescribed number of carries. One chooses long strings of repeated digits and analyzes the decimal form of

$$K(10^m-1).$$

The total decrease in digit sum caused by carries can be computed exactly, and by adjusting the repeated digit and the length of the block one forces the decrease to equal $(K-1)s(T)$. This yields infinitely many solutions.

The method used above is preferable because it converts the problem into a structural statement about repunits and periodic decimal expansions. Once a suitable block is found, infinitely many solutions arise immediately by concatenation, and the equality of digit sums becomes a consequence of the identity

$$10^{mt}-1=(10^m-1)(1+10^m+\cdots+10^{(t-1)m}).$$