Kvant Math Problem 1063

Verified: no
Verdicts: SKIP + SKIP
Solve time: 1m37s
Source on kvant.digital

Problem

How many distinct integers can be represented as the difference $a-\overline{a}$, where $a$ is a $n$-digit natural number ($10^{n-1}\le a\lt10^n$), and $\overline{a}$ is the number obtained by writing the digits of $a$ in reverse order? For example, if $a=1917$, then $a-\overline{a}=1917-7191=-5724$. Give the answer for:

1. $n=4$;
2. $n=5$;
3. any natural $n$.

G. O. Elsting

Exploration

Let the digits of the $n$-digit number $a$ be

$$a=d_{n-1}d_{n-2}\dots d_1d_0,$$

with $d_{n-1}\neq0$. Then

$$a-\overline a =\sum_{i=0}^{n-1} d_i(10^i-10^{n-1-i}).$$

The coefficients come in opposite pairs:

$$10^i-10^{n-1-i}=-(10^{n-1-i}-10^i).$$

Hence

$$a-\overline a =\sum_{i=0}^{m-1}(d_i-d_{n-1-i})(10^i-10^{n-1-i}),$$

where $m=\lfloor n/2\rfloor$.

For $n=4$,

$$a-\overline a =(d_0-d_3)(1-1000)+(d_1-d_2)(10-100)$$

and therefore

$$a-\overline a =-999(d_0-d_3)-90(d_1-d_2) =9\bigl(111x+10y\bigr),$$

where

$$x=d_3-d_0,\qquad y=d_2-d_1.$$

Since $x,y\in{-9,-8,\dots,9}$, the problem becomes counting the values of

$$111x+10y.$$

If

$$111x+10y=111x'+10y',$$

then

$$111(x-x')=10(y'-y).$$

The right-hand side has absolute value at most $180$, while the left-hand side is a multiple of $111$. Thus either $x=x'$ or $|x-x'|=1$. But if $|x-x'|=1$, then

$$|10(y'-y)|=111,$$

impossible. Hence the representation is unique. Therefore the number of values equals

$$19\cdot19=361.$$

For $n=5$,

$$a-\overline a =(d_0-d_4)(1-10000)+(d_1-d_3)(10-1000)$$

and

$$a-\overline a =9\bigl(1111x+110y\bigr) =99(101x+10y).$$

Again $x,y\in[-9,9]$. If

$$101x+10y=101x'+10y',$$

then

$$101(x-x')=10(y'-y).$$

The right-hand side has absolute value at most $180$, so $|x-x'|\le1$. The case $|x-x'|=1$ would give $|10(y'-y)|=101$, impossible. Thus uniqueness again holds, giving $361$ values.

For general $n$, write

$$a-\overline a =\sum_{i=0}^{m-1} c_i t_i,$$

where

$$c_i=d_{n-1-i}-d_i,\qquad t_i=10^{,n-1-i}-10^i.$$

Each $c_i$ can be any integer from $-9$ to $9$.

The crucial point is whether different vectors $(c_i)$ can give the same sum. Observe

$$t_i=10^i(10^{n-1-2i}-1).$$

Since $10^{k}-1$ is not divisible by $10$,

$$v_{10}(t_i)=i.$$

The coefficients $t_0,t_1,\dots,t_{m-1}$ therefore have distinct exact powers of $10$ dividing them.

Suppose

$$\sum_{i=0}^{m-1} e_i t_i=0,$$

with each $e_i\in[-18,18]$. Let $r$ be the smallest index with $e_r\neq0$. Dividing by $10^r$ gives

$$e_r(10^{n-1-2r}-1)+10M=0.$$

The first term is not divisible by $10$, because $10^{n-1-2r}-1\equiv -1\pmod{10}$, while $|e_r|\le18$ and $e_r\neq0$. Hence the left-hand side is not divisible by $10$, contradiction. Thus all $e_i=0$.

So the map $(c_i)\mapsto \sum c_i t_i$ is injective. Since each $c_i$ has $19$ possibilities, the number of values is

$$19^m,\qquad m=\left\lfloor\frac n2\right\rfloor .$$

The only remaining issue is realizability of every $c_i$. Taking

$$d_i=0,\ d_{n-1-i}=c_i$$

for $c_i\ge0$, and

$$d_i=-c_i,\ d_{n-1-i}=0$$

for $c_i<0$,

produces any prescribed $c_i$. If the leading digit becomes $0$, increase both digits in the outermost pair by the same amount; the difference $c_0$ is unchanged. Hence every coefficient vector occurs.

The count should therefore be $19^{\lfloor n/2\rfloor}$.

Problem Understanding

We must count how many distinct integers can occur in the form

$$a-\overline a,$$

where $a$ is an $n$-digit decimal number and $\overline a$ is obtained by reversing its digits.

This is a Type A problem. We must determine exactly the set size of all attainable values and prove both that at least that many values occur and that no more can occur.

The core difficulty is showing that different choices of digit differences cannot produce the same value of $a-\overline a$. The coefficients appearing in the expression have different $10$-adic orders, and this yields uniqueness.

The answer is

$$19^{\lfloor n/2\rfloor}.$$

For $n=4$ and $n=5$ this equals

$$19^2=361.$$

Intuitively, each symmetric pair of digits contributes an independent difference ranging from $-9$ to $9$, giving $19$ possibilities per pair, and these contributions combine without collisions.

Proof Architecture

Lemma 1. For every $n$,

$$a-\overline a =\sum_{i=0}^{m-1} c_i\bigl(10^{n-1-i}-10^i\bigr), \qquad m=\Bigl\lfloor\frac n2\Bigr\rfloor,$$

where $c_i=d_{n-1-i}-d_i$; this follows by pairing symmetric digit positions.

Lemma 2. Every vector $(c_0,\dots,c_{m-1})$ with $c_i\in{-9,\dots,9}$ is realizable by some $n$-digit number; construct suitable digit pairs.

Lemma 3. If

$$t_i=10^{n-1-i}-10^i,$$

then $v_{10}(t_i)=i$; factor out $10^i$ and use that $10^k-1$ is not divisible by $10$.

Lemma 4. If

$$\sum_{i=0}^{m-1} e_i t_i=0$$

with each $e_i\in[-18,18]$, then all $e_i=0$; choose the smallest index with nonzero coefficient and reduce modulo $10$ after dividing by the appropriate power of $10$.

Lemma 5. The map

$$(c_i)\longmapsto \sum c_i t_i$$

is injective; apply Lemma 4 to the difference of two representations.

The hardest direction is proving injectivity. Lemma 4 is the point most likely to fail under scrutiny.

Solution

Let

$$a=d_{n-1}d_{n-2}\dots d_1d_0,$$

where $d_{n-1}\neq0$. Then

$$a=\sum_{i=0}^{n-1}d_i10^i, \qquad \overline a=\sum_{i=0}^{n-1}d_i10^{n-1-i}.$$

Hence

$$a-\overline a =\sum_{i=0}^{n-1}d_i(10^i-10^{n-1-i}).$$

Put

$$m=\Bigl\lfloor\frac n2\Bigr\rfloor.$$

Combining the terms with indices $i$ and $n-1-i$ gives

$$a-\overline a =\sum_{i=0}^{m-1}(d_{n-1-i}-d_i) \bigl(10^{n-1-i}-10^i\bigr).$$

Define

$$c_i=d_{n-1-i}-d_i, \qquad t_i=10^{n-1-i}-10^i.$$

Then

$$a-\overline a=\sum_{i=0}^{m-1}c_it_i.$$

Since each digit lies between $0$ and $9$,

$$c_i\in{-9,-8,\dots,9}.$$

We first show that every such vector $(c_0,\dots,c_{m-1})$ is attainable.

If $c_i\ge0$, choose

$$d_i=0,\qquad d_{n-1-i}=c_i.$$

If $c_i<0$, choose

$$d_i=-c_i,\qquad d_{n-1-i}=0.$$

Then $d_{n-1-i}-d_i=c_i$ in either case. If the leading digit happens to be $0$, add the same positive integer to both digits of the outermost pair. Their difference remains $c_0$, and because both digits originally lie in $[0,9]$, such a choice can be made with the resulting digits still in $[0,9]$. Thus every vector $(c_i)$ occurs for some $n$-digit number.

Next we prove uniqueness.

For each $i$,

$$t_i=10^i(10^{n-1-2i}-1).$$

The factor $10^{n-1-2i}-1$ is congruent to $-1$ modulo $10$, hence not divisible by $10$. Therefore

$$v_{10}(t_i)=i.$$

Suppose

$$\sum_{i=0}^{m-1}e_it_i=0,$$

where each $e_i\in[-18,18]$.

Assume some $e_i$ is nonzero, and let $r$ be the smallest index with $e_r\neq0$. Dividing by $10^r$ yields

$$e_r(10^{n-1-2r}-1)+10M=0$$

for some integer $M$.

Since $10^{n-1-2r}-1\equiv-1\pmod{10}$,

$$e_r(10^{n-1-2r}-1)\equiv -e_r \pmod{10}.$$

Because $0<|e_r|\le18$, this term is not divisible by $10$. The term $10M$ is divisible by $10$. Their sum cannot be $0$, a contradiction. Hence all $e_i=0$.

Now suppose

$$\sum_{i=0}^{m-1}c_it_i = \sum_{i=0}^{m-1}c_i't_i.$$

Subtracting gives

$$\sum_{i=0}^{m-1}(c_i-c_i')t_i=0.$$

Each difference $c_i-c_i'$ belongs to $[-18,18]$. By the previous paragraph,

$$c_i-c_i'=0$$

for every $i$. Thus $c_i=c_i'$ for all $i$.

The correspondence

$$(c_0,\dots,c_{m-1}) \longmapsto a-\overline a$$

is therefore injective. Since every vector occurs and each $c_i$ has $19$ possible values, the number of distinct integers representable as $a-\overline a$ equals

$$19^m = 19^{\lfloor n/2\rfloor}.$$

For $n=4$,

$$19^{\lfloor4/2\rfloor}=19^2=361.$$

For $n=5$,

$$19^{\lfloor5/2\rfloor}=19^2=361.$$

Hence

$$\boxed{ \begin{aligned} n=4&:\ 361,\ n=5&:\ 361,\ \text{arbitrary }n&:\ 19^{\lfloor n/2\rfloor}. \end{aligned}}$$

Verification of Key Steps

The first delicate step is the claim that every vector $(c_i)$ is realizable. For a fixed pair of positions, any integer from $-9$ to $9$ can be written as $u-v$ with digits $u,v\in[0,9]$. The constructions $(u,v)=(c_i,0)$ for $c_i\ge0$ and $(0,-c_i)$ for $c_i<0$ verify this directly. The only global restriction is that the leading digit must be nonzero. Modifying both digits in the outermost pair by the same amount preserves their difference, so the prescribed value of $c_0$ is unchanged.

The second delicate step is proving $v_{10}(t_i)=i$. Writing

$$t_i=10^i(10^{n-1-2i}-1)$$

shows divisibility by $10^i$. Since

$$10^{n-1-2i}-1\equiv-1\pmod{10},$$

no further factor of $10$ is present. Thus the exact power of $10$ dividing $t_i$ is $10^i$.

The third delicate step is the injectivity argument. Let $r$ be the smallest index with $e_r\neq0$. After division by $10^r$, the contribution of index $r$ is

$$e_r(10^{n-1-2r}-1),$$

which is not divisible by $10$, whereas every remaining term is divisible by $10$. A cancellation to zero is impossible. The argument would fail if the coefficients $e_r$ could themselves contain arbitrarily large powers of $10$, but here $|e_r|\le18$, so a nonzero $e_r$ is never divisible by $10$.

Alternative Approaches

For $n=4$ and $n=5$, one may avoid the general injectivity lemma and work directly. For $n=4$,

$$a-\overline a=9(111x+10y),$$

and for $n=5$,

$$a-\overline a=99(101x+10y),$$

with $x,y\in[-9,9]$. A congruence argument modulo $10$ shows that two different pairs $(x,y)$ cannot yield the same value. Since there are $19^2$ pairs, there are $361$ values.

For general $n$, another approach is to regard the numbers

$$t_0,t_1,\dots,t_{m-1}$$

as a mixed radix system. Their exact $10$-adic orders are distinct, so the coefficients $c_i$ can be recovered successively from the residue classes modulo $10,10^2,\dots$. This also yields uniqueness. The proof using $10$-adic valuations is shorter because it packages the entire uniqueness argument into a single contradiction.