# A Problem of Divisibility by 2n

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

1. 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.