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\).
References
- J. B. Tabov and P. J. Taylor, Methods of Problem Solving, Book 1, Australian Mathematics Trust, 1996.
|Contact| |Front page| |Contents| |Arithmetic| |Math induction|
Copyright © 1996-2018 Alexander BogomolnyProve 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.
|Contact| |Front page| |Contents| |Generalizations| |Arithmetic| |Math induction|
Copyright © 1996-2018 Alexander Bogomolny71532864