Powers of TwoDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/