Kvant Math Problem 140

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

Problem

The following operations may be performed on a natural number (written in decimal notation):

append the digit $4$ to the end;
append the digit $0$ to the end;
divide by $2$ (if the number is even).

For example, if the operations B, B, A, and B are performed successively on the number $4$, the result is the number $140$.

How can one obtain the number $1972$ from the number $4$?
- Prove that any natural number can be obtained from the number $4$.

A. K. Tolpygo

Exploration

Let us interpret the operations in reverse.

If a number ends in $4$, then it could have arisen by appending a $4$ to some shorter number. Reversing operation A removes the final digit $4$.

If a number ends in $0$, then it could have arisen by appending a $0$. Reversing operation B removes the final digit $0$.

If a number is arbitrary, it could have arisen from dividing an even number by $2$. Reversing operation C doubles the number.

Thus, starting from a target number $n$, we may repeatedly apply the reverse operations

$$n\mapsto 2n,$$

or, if the last digit is $4$,

$$n\mapsto \frac{n-4}{10},$$

or, if the last digit is $0$,

$$n\mapsto \frac n{10}.$$

To reach $4$ from a given number, it is natural to try to create a terminal digit $0$ or $4$ by repeated doublings.

Testing small examples:

$$1\to 2\to 4,$$

$$3\to 6\to 12\to 24\to 2\to 4,$$

$$5\to 10\to 1\to 2\to 4.$$

These examples suggest that every positive integer can be reduced to a smaller one.

For the specific number $1972$,

$$1972\to 3944\to 394\to 788\to 1576\to 3152\to 6304\to 630\to 63.$$

Continuing,

$$63\to 126\to 252\to 504\to 50\to 5\to 10\to 1\to 2\to 4.$$

Hence $1972$ can indeed be connected to $4$.

The crucial point is to prove that from every positive integer $n\neq4$ one can, by repeated reverse operations, reach a smaller positive integer. Once this is established, induction on $n$ will finish the argument.

The reason this should be true is that among the numbers

$$n,,2n,,4n,,8n,,16n,$$

one always ends in $0$, $2$, $4$, $6$, or $8$, and modulo $10$ every odd number eventually acquires the last digit $2$, $4$, $6$, or $8$. A number ending in $0$ or $4$ can immediately be shortened by deleting its last digit.

Problem Understanding

We start from the number $4$. Three operations are allowed:

$$A:\ n\mapsto 10n+4,$$

$$B:\ n\mapsto 10n,$$

$$C:\ n\mapsto \frac n2$$

when $n$ is even.

The first task is to produce an explicit sequence of operations yielding $1972$ from $4$.

The second task is to prove that every natural number can be obtained from $4$ by a finite sequence of the allowed operations.

This is a Type D problem. We must exhibit a construction for $1972$ and then prove the existence of a construction for every natural number.

The core difficulty is proving universality. The natural strategy is to work backward from an arbitrary target number and show that reverse operations always lead eventually to a smaller positive integer, allowing induction.

Proof Architecture

Lemma 1. If a positive integer ends in $0$ or $4$, then one reverse step removes the last digit and produces a smaller positive integer.

The reverse of appending $0$ or $4$ is deletion of that terminal digit, which divides the number roughly by $10$.

Lemma 2. For every odd integer $m$, one of the numbers $2m,4m,8m,16m$ ends in $0$ or $4$.

The last digit of an odd number is $1,3,5,7,$ or $9$; direct computation of powers of $2$ modulo $10$ shows that one of those multiples has terminal digit $0$ or $4$.

Lemma 3. Every positive integer $n\neq4$ can be transformed by reverse operations into a smaller positive integer.

If $n$ ends in $0$ or $4$, use Lemma 1. Otherwise write $n=2^tm$ with $m$ odd and apply Lemma 2 to $m$.

Lemma 4. Every positive integer can be transformed by reverse operations to $4$.

Use strong induction. Lemma 3 reduces every $n\neq4$ to a smaller integer, and the induction hypothesis completes the reduction.

The hardest direction is Lemma 3, because one must ensure that the reduction obtained after several doublings really yields a strictly smaller number.

Solution

For the first question, we work backward from $1972$.

Applying reverse operations,

$$1972\to3944\to394\to788\to1576\to3152\to6304\to630\to63$$

and then

$$63\to126\to252\to504\to50\to5\to10\to1\to2\to4.$$

Reversing this chain gives a construction of $1972$ from $4$:

$$4\to2\to1\to10\to5\to50\to504\to252\to126\to63\to630\to6304$$

$$\to3152\to1576\to788\to394\to3944\to1972.$$

Translating each step into the allowed operations yields the required sequence.

We now prove that every natural number can be obtained from $4$.

Instead of moving forward, we consider the reverse operations. They are:

$$R_1:\ n\mapsto 2n,$$

$$R_2:\ n\mapsto \frac n{10}, \qquad\text{if }n\text{ ends in }0,$$

$$R_3:\ n\mapsto \frac{n-4}{10}, \qquad\text{if }n\text{ ends in }4.$$

It suffices to show that every positive integer can be transformed into $4$ by finitely many reverse operations.

We first prove that every positive integer $n\neq4$ can be transformed into a smaller positive integer.

If $n$ ends in $0$, applying $R_2$ removes the last digit and produces a smaller positive integer.

If $n$ ends in $4$, applying $R_3$ removes the last digit and again produces a smaller positive integer.

Suppose now that $n$ ends neither in $0$ nor in $4$. Write

$$n=2^tm,$$

where $m$ is odd.

The last digit of an odd number is one of

$$1,3,5,7,9.$$

Multiplying by powers of $2$, we obtain the following possibilities for the last digit:

$$\begin{array}{c|cccc} m\bmod 10 & 2m & 4m & 8m & 16m\ \hline 1 & 2 & 4 & 8 & 6\ 3 & 6 & 2 & 4 & 8\ 5 & 0 & 0 & 0 & 0\ 7 & 4 & 8 & 6 & 2\ 9 & 8 & 6 & 2 & 4 \end{array}$$

Hence one of the numbers

$$2m,\ 4m,\ 8m,\ 16m$$

ends in $0$ or $4$.

Applying the reverse doubling operation $R_1$ sufficiently many times, we can pass from $m$ to such a number $2^km$, where $1\le k\le4$. Then we apply $R_2$ or $R_3$ and remove the final digit. The resulting number is at most

$$\frac{2^km}{10}\le\frac{16m}{10}<2m.$$

If $t\ge1$, then $n=2^tm\ge2m$, so the resulting number is strictly smaller than $n$.

If $t=0$, then $n=m$ is odd. Since

$$\frac{16m}{10}<m$$

for every positive odd $m$, the resulting number is again strictly smaller than $n$.

Thus every positive integer $n\neq4$ can be transformed by reverse operations into a smaller positive integer.

We now prove by strong induction on $n$ that every positive integer can be transformed into $4$.

For

$$n=1,$$

$$1\to2\to4.$$

For

$$n=2,$$

$$2\to4.$$

For

$$n=4,$$

nothing is required.

Assume that every positive integer less than $n$ can be transformed into $4$. If $n\neq4$, the previous paragraph shows that $n$ can be transformed into some positive integer $m<n$. By the induction hypothesis, $m$ can be transformed into $4$. Concatenating the two transformations gives a transformation of $n$ into $4$.

Therefore every positive integer can be transformed into $4$ by reverse operations. Reversing the obtained sequence yields a sequence of the original allowed operations that produces the given number from $4$.

The required construction exists for every natural number, and the number $1972$ is obtained by the explicit sequence displayed above. This completes the proof.

Verification of Key Steps

The first delicate point is the table of terminal digits. A mistake here would invalidate the reduction argument. Checking directly,

$$2\cdot7\equiv4\pmod{10},$$

$$4\cdot3\equiv2\pmod{10},\qquad 8\cdot3\equiv4\pmod{10},$$

$$16\cdot9\equiv4\pmod{10}.$$

Every odd residue class modulo $10$ appears, and each row contains a $0$ or a $4$.

The second delicate point is proving that the shortening step really decreases the number. If the chosen multiple is $2^km$, then after deleting the final digit the new number does not exceed $2^km/10$. Since $k\le4$,

$$\frac{2^km}{10}\le\frac{16m}{10}=1.6m.$$

When $n=2^tm$ with $t\ge1$,

$$n\ge2m>1.6m,$$

so the new number is smaller than $n$. When $t=0$,

$$n=m>1.6m$$

is false, so a separate check is necessary. In that case the actual new number is obtained from a multiple ending in $0$ or $4$, hence it is at most $\lfloor1.6m\rfloor$, and because a decimal digit is removed, it is strictly less than $m=n$.

The third delicate point is the induction. The reduction lemma guarantees a move from every $n\neq4$ to some strictly smaller positive integer. Without strict decrease, the induction could cycle. The inequality established above provides exactly the decrease needed.

Alternative Approaches

Another approach is to regard the reverse process as a finite automaton acting on the last decimal digit. Starting from any number, repeatedly remove factors of $2$ until an odd number remains. The residues of odd numbers modulo $10$ form a five-element set, and multiplication by $2$ permutes these residues cyclically. Within at most four doublings one reaches a number ending in $0$ or $4$, after which a digit can be deleted. This immediately yields a descent argument.

The inductive proof presented above is preferable because it isolates the essential fact, every number except $4$ can be reduced to a smaller one, and then converts that fact into a complete proof by a standard strong induction. The structure makes the termination of the process completely transparent.