I have a problem with the solution for the (b) part of the problem. The problem is as follows:
Let $n$ be a natural number. Prove that $2^n$ has a multiple whose representation contains only ones and twos.
Solution is this : "It's perhaps easiest to show by induction on $k$ that there is a $k$-digit number containing only ones and twos which is a multiple of $2^k$. Adding a $1$ or a $2$ to the front of such a number increments it by $2^k5^k$ or by $2^{k+1}5^k$, in each case preserving division by $2^k$; since the two choices differ by $2^k 5^k$, one of them must actually achieve divisibility by $2^{k+1}$."
I am unable to understand the last part which says "one of them must actually achieve divisibility by $2^{k+1}$."
My question is why?
I was able to understand it. Posting my explanation for reference as well.
Let's say the original multiple of $2^k$ is m. if we add a 1 to its front the new number is $m+2^k * 5^k$ , and if we add a 2 to its front the new number is $m+2*2^k*5^k$
since m is divisible by $2^k$ we can write the new number as $2^k(q + 5^k)$ or $2^k(q+2*5^k)$ where $q = m/2^k$
Now $q$ can be even or odd. Thus, the term inside the bracket is either even or odd because in one case we are adding an odd number to $q$ and in another we are adding an even number. So there has to be another '2' in the bracket term's factorization which means one of these two terms will be divided by $2*2^k$ by giving us an additional $2$ in the factorization. We already have $2^k$ in it.