A Problem of Divisibility by 2ⁿ

The following problem relates to the sequence A126933 in the Online Encyclopedia of Integer Sequences, which apparently underlied a problem posed at the 1971 All (Soviet) Union Mathematical Olympiad. The problem has been posted at Ben Vitale's blog:

Prove that among \(n\)-digit numbers whose decimal expansion consists solely of digits \(1\) and \(2\) there is one and only one divisible by \(2^n\).

Solution

References

J. B. Tabov and P. J. Taylor, Methods of Problem Solving, Book 1, Australian Mathematics Trust, 1996.

Prove that among \(n\)-digit numbers whose decimal expansion consists solely of digits \(1\) and \(2\) there is one and only one divisible by \(2^n\).

Proof

We prove by induction that the residues of division by \(2^n\) of the \(n\)-digit decimal numbers written with \(1\)s and \(2\)s are all different. Since there are exactly \(2^n\) such numbers, the result follows.

For \(n=1\), there are just two \(1\)-digit numbers: \(1\equiv 1\space (\mbox{mod}\space 2^{1})\) and \(2\equiv 0\space (\mbox{mod}\space 2^{1})\). Assume that the assertion holds for \(n=k\) and consider the residue of \(10^k\space (\mbox{mod}\space 2^{k+1})\). Let \(10^{k}=2^{k+1}m+c\), where \(0\le c\lt 2^{k+1}\).

First of all, since \(10^{k}=2^{k}5^{k}\), \(c\equiv 0\space (\mbox{mod}\space 2^{k})\). In other words, either \(c=0\) or \(c=2^k\). The former is impossible because it would imply \(5^{k}=2m\). Therefore, \(c=2^k\) and \(10^{k}=2^{k+1}m+2^k\), resulting in an implication,

\( a \equiv b\space (\mbox{mod}\space 2^{k})\space\Rightarrow\space 1a \equiv b+2^{k}\space (\mbox{mod}\space 2^{k+1}), \)

where, for a \(k\)-digit number \(a\), \(1a\) is the (k+1)-digit number obtained by prepending \(1\) to \(a\).

Similarly, \(2a \equiv b+0\space (\mbox{mod}\space 2^{k+1})\), because \(2\cdot 10^{k}=2^{k+1}5^k\).

Now, all residues modulo \(2^k\) are less than \(2^k\), so adding to them \(2^k\) leads to the set \(\{2^{k}, 2^{k}+1,\ldots,2^{k+1}-1\}\), such that together they generate all the residues modulo \(2^{k+1}\), and, therefore, each only once.

71532864

A Problem of Divisibility by 2n

References

Proof

A Problem of Divisibility by 2ⁿ