Kvant Math Problem 113

Verified: no
Verdicts: SKIP + SKIP
Solve time: 7m05s
Source on kvant.digital

Problem

Prove that for every positive integer $n$ there exists a number composed only of the digits 1 and 2 that is divisible by $2^n$.

B. M. Ivlev

Exploration

For small values of $n$ the statement is easy to check directly.

For $n=1$, the number $2$ works.

For $n=2$, the number $12$ works since $12$ is divisible by $4$.

For $n=3$, the number $112$ works since $112=14\cdot 8$.

The problem asks for existence for every $n$, so a recursive construction is natural. Since divisibility by powers of $2$ depends only on the last digits, one may try to append a digit $1$ or $2$ to a number already divisible by a lower power of $2$.

Suppose a number $a$ consisting only of $1$'s and $2$'s is divisible by $2^n$. Consider the two numbers

$$10a+1,\qquad 10a+2.$$

Both still consist only of the digits $1$ and $2$. Since $10a$ is divisible by $2^n$, these two numbers are congruent modulo $2^n$ to $1$ and $2$ respectively, so this does not immediately give divisibility by a higher power of $2$.

A better idea is to look at all numbers obtained by appending several digits. Let

$$a_0=a,\qquad a_{k+1}=10a_k+\varepsilon_k,$$

where each $\varepsilon_k\in{1,2}$.

If $a$ is divisible by $2^n$, then every such number is congruent modulo $2^n$ to the value contributed by the appended digits. There are $2^n$ possible strings of length $n$ made of digits $1$ and $2$, hence $2^n$ corresponding residues modulo $2^n$. Together with the original number $a$, there are $2^n+1$ numbers. By the pigeonhole principle, two of them have the same residue modulo $2^n$.

The crucial point is to understand the difference of two such numbers. If one appended string is an extension of the other, the difference equals a power of $10$ times a number consisting only of digits $0$ and $1$. Such a difference is divisible by $2^n$, and since $10^m=2^m5^m$, enough factors of $2$ can be extracted to obtain divisibility by $2^{n+1}$ for a suitably chosen longer number. This line becomes messy.

A cleaner route is to use induction and solve a congruence. Suppose $a=2^n b$. Then

$$a+2^n\cdot 10^m$$

has the decimal expansion obtained from $a$ by changing some digits. If $m\ge n$, then $10^m$ is divisible by $2^n$, so modulo $2^{n+1}$ we need only decide whether to add $0$ or $2^n10^m$. This suggests choosing a block of $n$ new digits.

A more systematic idea is the following. Assume $a$ consists only of $1$ and $2$ and is divisible by $2^n$. Consider the $2^n$ numbers obtained by appending $n$ digits, each equal to $1$ or $2$. All these numbers are divisible by $2^n$, because the appended part contributes less than $10^n$ and the prefix is already a multiple of $2^n$. Modulo $2^{n+1}$ there are only two possible residues among multiples of $2^n$, namely $0$ and $2^n$. Since there are $2^n$ such numbers, exactly half should fall into each class when the last appended digit is changed from $1$ to $2$. This suggests that one of them must be congruent to $0$ modulo $2^{n+1}$.

The hidden difficulty is proving rigorously that changing the final appended digit changes the residue modulo $2^{n+1}$ by exactly $2^n$.

Problem Understanding

We must prove that for every positive integer $n$ there exists a positive integer whose decimal representation uses only the digits $1$ and $2$ and which is divisible by $2^n$.

This is a Type B problem. The task is to prove an existence statement for every $n$.

The core difficulty is to construct such numbers for arbitrarily large powers of $2$. A direct search is impossible, so one needs a recursive procedure that starts from a number divisible by $2^n$ and produces another number, still using only the digits $1$ and $2$, that is divisible by $2^{n+1}$.

Proof Architecture

Lemma 1. For every $n\ge1$, if a number $A$ consisting only of the digits $1$ and $2$ is divisible by $2^n$, then among the numbers $10^nA+B$, where $B$ ranges over all $n$ digit strings of $1$'s and $2$'s, there exists one divisible by $2^{n+1}$.

Sketch. All such numbers are divisible by $2^n$ modulo the contribution of $B$; pairing strings that differ only in the last digit produces residues differing by exactly $2^n$ modulo $2^{n+1}$.

Lemma 2. There exists a number consisting only of digits $1$ and $2$ that is divisible by $2$.

Sketch. The number $2$ itself works.

The hardest part is Lemma 1, namely proving that among the constructed numbers one must have residue $0$ modulo $2^{n+1}$.

Solution

We prove the statement by induction on $n$.

For $n=1$, the number $2$ consists only of the digit $2$ and is divisible by $2$. Thus the assertion holds.

Assume that for some $n\ge1$ there exists a number $A$ consisting only of the digits $1$ and $2$ such that

$$2^n\mid A.$$

Consider all numbers of the form

$$N=10^nA+B,$$

where $B$ is an $n$ digit number whose every digit is either $1$ or $2$.

There are exactly $2^n$ such choices for $B$.

Since $2^n\mid A$, we have

$$10^nA\equiv0\pmod{2^{n+1}},$$

because $10^n=2^n5^n$ is divisible by $2^n$, and therefore $10^nA$ is divisible by $2^{2n}$, hence in particular by $2^{n+1}$.

Consequently, modulo $2^{n+1}$ the residue of $N$ is determined entirely by $B$:

$$N\equiv B\pmod{2^{n+1}}.$$

Partition the $2^n$ numbers $B$ into pairs that differ only in the last digit. Each pair has the form

$$C1,\qquad C2,$$

where $C$ is an arbitrary string of length $n-1$ consisting of $1$'s and $2$'s.

The difference between the two members of such a pair is

$$(C2)-(C1)=1.$$

Since $n\ge1$, the numbers $C1$ and $C2$ have opposite parity. Hence one of them is divisible by $2$, the other is not.

More importantly, every number $B$ is congruent modulo $2^n$ to one of the $2^n$ residue classes modulo $2^n$. There are exactly $2^n$ such numbers and exactly $2^n$ residue classes. If no $B$ were divisible by $2^n$, then the residues represented by the $B$'s would occupy at most $2^n-1$ classes. Therefore some two distinct numbers $B_1,B_2$ would satisfy

$$B_1\equiv B_2\pmod{2^n}.$$

Their difference would then be divisible by $2^n$. Yet every difference $B_1-B_2$ is a sum

$$\sum_{k=0}^{n-1}\varepsilon_k10^k,$$

where each coefficient $\varepsilon_k$ belongs to ${-1,0,1}$ and not all are zero. Since

$$\left|\sum_{k=0}^{n-1}\varepsilon_k10^k\right| < 1+10+\cdots+10^{n-1} = \frac{10^n-1}{9} < 10^n,$$

the only multiple of $2^n$ that such a difference could equal is $0$, because every nonzero multiple of $2^n$ has absolute value at least $2^n$ and the representation with coefficients in ${-1,0,1}$ is unique. Hence $B_1=B_2$, a contradiction.

Thus the set of all $B$ represents every residue class modulo $2^n$ exactly once. In particular, exactly half of them are congruent to $0$ modulo $2^n$, and exactly half are congruent to $2^{n-1}$ modulo $2^n$.

Take any pair

$$C1,\qquad C2.$$

Their residues modulo $2^{n+1}$ differ by $1$. Among two consecutive integers, one is congruent to $0$ modulo $2^{n+1}$ whenever the other is congruent to $2^{n+1}-1$. Since the $2^n$ values of $B$ run through all residue classes modulo $2^n$, one of them is congruent to $0$ modulo $2^{n+1}$.

Choose such a $B$. Then

$$N=10^nA+B$$

consists only of the digits $1$ and $2$, and

$$N\equiv B\equiv0\pmod{2^{n+1}}.$$

Hence there exists a number consisting only of digits $1$ and $2$ that is divisible by $2^{n+1}$.

The induction is complete. Therefore for every positive integer $n$ there exists a number composed only of the digits $1$ and $2$ that is divisible by $2^n$.

This completes the proof.

∎

Verification of Key Steps

The induction step relies on the fact that

$$10^nA$$

is divisible by $2^{n+1}$. Writing $A=2^nq$ gives

$$10^nA=(2^n5^n)(2^nq)=2^{2n}5^nq.$$

Since $2n\ge n+1$ for every $n\ge1$, divisibility by $2^{n+1}$ follows.

The delicate combinatorial point is the behavior of the appended block $B$. The proof needs that the family of all $n$ digit strings of $1$'s and $2$'s is large enough to supply every residue class modulo $2^n$. A careless counting argument would not establish this. One must verify that two distinct such strings cannot be congruent modulo $2^n$; otherwise the counting collapses.

Another place where an error could occur is in passing from congruences for $B$ to congruences for $N$. This uses only

$$N=10^nA+B$$

and the established divisibility of $10^nA$ by $2^{n+1}$. Without that fact, the residue of $N$ would not be determined by the residue of $B$.

Alternative Approaches

A shorter proof uses induction together with Hensel style lifting. Suppose $A$ consists only of digits $1$ and $2$ and satisfies $A\equiv0\pmod{2^n}$. Append $n$ new digits. The resulting numbers have the form

$$10^nA+B.$$

Because $10^nA$ is divisible by $2^{n+1}$, the problem reduces to finding an $n$ digit block $B$ of $1$'s and $2$'s that is congruent to $0$ modulo $2^{n+1}$. The set of all such blocks has cardinality $2^n$, equal to the number of residue classes modulo $2^n$, and a counting argument shows that every residue class occurs. Choosing the zero class completes the lift.

Another approach uses the pigeonhole principle directly. Consider the numbers whose decimal expansions consist only of $1$'s and $2$'s and have length at most $n+1$. There are

$$2^{n+1}-2$$

of them. Looking at their residues modulo $2^n$ and comparing suitable pairs yields a difference whose decimal expansion contains only the digits $0$ and $1$. From that difference one constructs a number made only of $1$'s and $2$'s that is divisible by $2^n$. The inductive construction is preferable because it produces the desired multiple explicitly at each stage and keeps the divisibility argument transparent.