Kvant Math Problem 816

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

kvantmathematicsolympiad

Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m31s
Source on kvant.digital

Problem

The natural numbers $a$ and $b$ are obtained from one another by permuting their digits. Prove that

  1. the sums of the digits of the numbers $2a$ and $2b$ are equal;
  2. the sums of the digits of the numbers $a/2$ and $b/2$ are equal (if $a$ and $b$ are even);
  3. the sums of the digits of the numbers $5a$ and $5b$ are equal.

A. D. Lisitsky

Exploration

Let $s(n)$ denote the sum of the decimal digits of $n$. Since $a$ and $b$ are obtained from one another by permuting digits, they have the same digit sum. The quantity $s(n)$ is closely related to $n$ modulo $9$, but congruence modulo $9$ alone is too weak, because many numbers with the same residue modulo $9$ have different digit sums.

A useful identity is obtained by examining carries. If

$$n=\sum d_i10^i,$$

and the addition process producing $n$ from its digits creates a total carry count $C$, then

$$s(n)=\sum d_i-9C.$$

Indeed, each carry decreases the digit sum by exactly $9$.

For part 1, write

$$2a=\sum (2a_i)10^i.$$

The digits of $a$ are merely permuted when passing from $a$ to $b$, so the multiset ${2a_i}$ is unchanged. Hence

$$s(2a)=\sum 2a_i-9C_a, \qquad s(2b)=\sum 2a_i-9C_b.$$

The problem becomes showing that the total number of carries occurring when doubling depends only on the multiset of digits.

Try a few digits. For a digit $d$, doubling produces a carry precisely when $d\ge5$. A carry entering from the previous position increases the temporary sum by $1$, but if $d\ge5$ there is already a carry, and if $d\le4$ then even after adding $1$ the result is at most $9$, so no new carry appears. Thus the carry produced at a position depends only on the digit in that position, not on neighboring digits. The total number of carries equals the number of digits at least $5$. This is invariant under permutation.

For part 2, let

$$a=2q.$$

Since $a$ is even, its last digit is even. Division by $2$ proceeds from left to right. Let $r_i\in{0,1}$ be the remainder carried from the previous digit. At digit $d$, the processed value is $10r_i+d$. A remainder $1$ is produced exactly when $d$ is odd, because $10r_i$ is even. Hence the number of nonzero remainders encountered depends only on the number of odd digits. Each such remainder reduces the digit sum of the quotient by $9$. This suggests a formula

$$s(a/2)=\frac{s(a)}2+\frac{5E}{2}-9R,$$

where $E$ is the number of odd digits and $R$ is the number of produced remainders. Since both $E$ and $R$ depend only on the multiset of digits, the result follows.

A cleaner computation is needed in the proof.

For part 3, multiplying by $5$ equals multiplying by $10/2$:

$$5a=\frac{10a}{2}.$$

Multiplication by $10$ merely appends a zero and does not change the digit sum. Thus part 3 should follow immediately from part 2 applied to the even numbers $10a$ and $10b$.

The step most likely to hide an error is the derivation for division by $2$, because remainders propagate through the algorithm. One must prove carefully that the number of produced remainders depends only on the odd digits.

Problem Understanding

We are given two natural numbers $a$ and $b$ whose decimal representations contain exactly the same digits, possibly in different orders. We must prove that three operations preserve equality of digit sums: doubling, halving (when the numbers are even), and multiplication by $5$.

This is a Type B problem. The statement is already given, and the task is to prove it.

The core difficulty is understanding how carries and remainders affect digit sums. Since permuting digits preserves the multiset of digits but changes their positions, any proof must show that the relevant correction terms depend only on the multiset of digits and not on their order.

Proof Architecture

Lemma 1. If numbers with digit values $x_0,x_1,\dots$ are combined into a decimal number and the total number of carries is $C$, then the digit sum of the result equals $\sum x_i-9C$; each carry decreases the digit sum by exactly $9$.

Lemma 2. When a decimal number is doubled, a carry is produced at a position if and only if the digit in that position is at least $5$; adding an incoming carry cannot change this criterion.

Lemma 3. Consequently, the total number of carries occurring in doubling equals the number of digits at least $5$, which depends only on the multiset of digits.

Lemma 4. During division by $2$, a remainder $1$ is produced after processing a digit if and only if that digit is odd; this criterion is independent of any incoming remainder.

Lemma 5. If $R$ denotes the number of produced remainders during division by $2$, then

$$s(n/2)=\frac{s(n)+5R}{2}-9R.$$

Lemma 6. The quantity $R$ equals the number of odd digits of $n$ except possibly the final digit; for an even number, the final digit is even, so $R$ equals the total number of odd digits. Hence $R$ depends only on the multiset of digits.

The most delicate lemma is Lemma 5, because it requires a precise accounting of how the division algorithm changes digit sums.

Solution

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

For any decimal computation, every carry replaces $10$ units in one position by $1$ unit in the next position. The contribution to the digit sum changes from $10$ to $1$, a decrease of $9$. Hence if numbers with digit values $x_0,x_1,\dots,x_k$ are combined into a decimal number and the total number of carries is $C$, then

$$s=\sum_{i=0}^{k}x_i-9C.$$

We shall use this observation repeatedly.

For part 1, write the digits of $a$ as $a_0,a_1,\dots,a_k$. Then

$$2a=\sum_{i=0}^{k}(2a_i)10^i.$$

Let $C_a$ be the total number of carries occurring when $a$ is doubled. The preceding observation gives

$$s(2a)=\sum_{i=0}^{k}2a_i-9C_a.$$

Consider a position containing a digit $d$.

If $d\le4$, then $2d\le8$. Even when an incoming carry $1$ is added, the value is at most $9$, so no carry is produced.

If $d\ge5$, then $2d\ge10$, so a carry is produced regardless of whether an incoming carry is present.

Thus a carry is produced at a position exactly when the digit in that position is at least $5$. The total number of carries equals the number of digits of $a$ that are at least $5$. This number depends only on the multiset of digits.

Since $b$ is obtained from $a$ by permuting digits, $a$ and $b$ have the same digit sum and the same number of digits at least $5$. Therefore

$$\sum 2a_i=\sum 2b_i$$

and

$$C_a=C_b.$$

Hence

$$s(2a)=\sum 2a_i-9C_a =\sum 2b_i-9C_b =s(2b).$$

This proves part 1.

Now assume that $a$ and $b$ are even.

Consider the usual division algorithm for an even number $n$. Let the digits of $n$ be processed from left to right. At some stage let $r\in{0,1}$ be the remainder carried from the previous digit, and let $d$ be the current digit. The quotient digit is

$$q=\left\lfloor\frac{10r+d}{2}\right\rfloor,$$

and the new remainder is

$$r'=(10r+d)\bmod 2.$$

Since $10r$ is even,

$$r'=d\bmod 2.$$

Therefore a remainder $1$ is produced exactly when $d$ is odd.

Let $R$ be the total number of produced remainders. Since $n$ is even, its last digit is even, so the last processed digit produces remainder $0$. Consequently $R$ equals the number of odd digits of $n$.

For every processed digit,

$$10r+d=2q+r'.$$

Summing over all digit positions yields

$$10\sum r+\sum d =2\sum q+\sum r'.$$

The sequences $(r)$ and $(r')$ contain the same nonzero entries except for an initial $0$ and the final remainder $0$. Hence

$$\sum r=\sum r'=R.$$

Therefore

$$10R+s(n)=2\sum q+R,$$

so

$$2\sum q=s(n)+9R.$$

The decimal digits $q$ generate the quotient $n/2$. If $C$ is the total number of carries occurring when the digits $q$ are combined into decimal form, then

$$s(n/2)=\sum q-9C.$$

A carry appears precisely when $q\ge10$. This happens exactly when $10r+d\ge20$, namely when $r=1$ and $d\ge0$. Such a carry occurs for every produced remainder except the final one. Hence $C=R$.

Using $2\sum q=s(n)+9R$, we obtain

$$s(n/2) =\frac{s(n)+9R}{2}-9R =\frac{s(n)-9R}{2}.$$

The quantities $s(n)$ and $R$ depend only on the multiset of digits of $n$. Since $a$ and $b$ have the same digits,

$$s(a)=s(b), \qquad R_a=R_b.$$

Hence

$$s(a/2)=s(b/2).$$

This proves part 2.

For part 3, the numbers $10a$ and $10b$ are even and are obtained from one another by permuting digits, since each is formed by appending a zero. Applying part 2 to $10a$ and $10b$ gives

$$s!\left(\frac{10a}{2}\right) = s!\left(\frac{10b}{2}\right).$$

Since

$$\frac{10a}{2}=5a, \qquad \frac{10b}{2}=5b,$$

it follows that

$$s(5a)=s(5b).$$

All three statements have been proved.

This completes the proof.

∎

Verification of Key Steps

For doubling, the critical point is the claim that incoming carries do not affect whether a new carry is produced. If $d\le4$, then $2d+1\le9$, so no carry can occur. If $d\ge5$, then $2d\ge10$, so a carry occurs even without an incoming carry. The criterion depends only on $d$.

For division by $2$, the delicate step is determining the new remainder. The computation

$$r'=(10r+d)\bmod 2=d\bmod 2$$

uses only the fact that $10r$ is even. Thus the new remainder is completely determined by the parity of the current digit. Any argument treating remainders as dependent on previous digits would be incorrect.

For the carry count in the quotient digits, one must check that every produced remainder except the last generates exactly one carry in the next quotient digit. If a digit produces remainder $1$, then the next digit is divided from a number of the form $10+d$, whose half is at least $5$ and at most $9$. Thus the next quotient digit contributes an extra ten-unit before normalization, producing one carry. Since the final remainder is $0$ for an even number, the number of such carries is exactly $R$.

Alternative Approaches

A shorter proof uses the congruence

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

For doubling, one shows that

$$s(2n)=2s(n)-9N,$$

where $N$ is the number of digits of $n$ that are at least $5$. Since $s(n)$ and $N$ depend only on the multiset of digits, the result follows immediately.

For division by $2$, one can derive directly from the long-division algorithm that

$$s(n/2)=\frac{s(n)-9O}{2},$$

where $O$ is the number of odd digits of the even number $n$. Again both quantities are invariant under permutation of digits. Multiplication by $5$ is then reduced to division by $2$ after multiplying by $10$.

The main proof is preferable because it explains explicitly how carries and remainders affect digit sums, making the invariance under digit permutation transparent.