Powers of Two

Date: 05/29/97 at 12:40:17
From: Jose A. Cofre
Subject: Number theory ?

I will be participating in the 36th annual school mathematics 
competition.I have a sample question and I am totally stumped:

Prove that every power of 2 has a multiple whose decimal expansion has 
only digits 1 and 2.  For example, 3*2^2 = 12 and 14*2^3 = 112.

I have considered that 2^2, 2^3, 2^4... make a geometric sequence, so 
I have used the formula for the nth term of a geometric progression: 
Tn = ar^n-1, where a is the first term and r is the common ratio.  
So my equation is: ar^n-1*(integer) = ?  I don't know if this is 
correct, but I don't even know how to describe the decimal expansion 
with digits only 1 and 2.

Thank for helping me,  
Joe

Date: 05/29/97 at 17:41:47
From: Doctor Wilkinson
Subject: Re: Number theory ?

Dear Joe, 

This is a cute problem!

I think you're best off trying to prove it by induction.  As you 
noticed:

        2 is a multiple of 2
       12 is a multiple of 4
      112 is a multiple of 8

I seem to be able to continue this:

     2112 is a multiple of 16
    22112 is a multiple of 32

So it seems as if I can just keep tacking digits on on the left, okay?  
That is, I don't seem to have to scramble up the digits I've already 
got to get up to the next power of 2.  Let's see if we can prove that 
this will work.

Suppose we have a k-digit number consisting of just 1's and 2's which 
is divisible by 2^k.  We want to tack a 1 or a 2 on to the left to get 
a number that's divisible by 2^(k+1). 

Now 10^k is divisible by 2^k, so 2*10^k is divisible by 2^(k+1). 
If the k-digit number is already divisible not only by 2^k but by 
2^(k+1), we can add a 2 on the left and get a number that will be 
divisble by 2^(k+1).  

The other possibility is that the k-digit number is divisible by 2^k 
but not by 2^(k+1).  That means that when we divide it by 2^k we get 
an odd number, so it's of the form:

 2^k (2x + 1)

What happens if we add a 1 on the left?  That adds 10^k, so we 
have:

 10^k + 2^k (2x + 1) =
 10^k + 2^(k+1) x + 2^k =

 2^(k+1) x + 2^k * 5^k + 2^k =

 2^(k+1) x + 2^k (5^k + 1)

5^k + 1 is even, so it's of the form 2y and we have:

 2^(k+1) x + 2^k (2y) = 2^(k+1) + 2^(k+1) y,

which is a multiple of 2^(k+1) and we have succeeded!

-Doctor Wilkinson,  The Math Forum
 Check out our web site!  http://mathforum.org/dr.math/