Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

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/   
    
Associated Topics:
High School Puzzles

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/