Find a 13 digit positive integer N whose base ten representation consists entirely of 8s and 9s
such that 2^{13} divides N.
(In reply to
answers spoiler by Ady TZIDON)
Originally, I couldn't figure out what your inductive proof was, but after thinking about it I filled it in:
It's always possible to add an 8 or a 9 to the left of a given string representing a number formed from 8's and 9's so that the complete number is divisible by 2^n, where n is the number of digits in the new string (number).
8 is divisible by 2^1 = 2.
Let xxx be any (n1)digit number divisible by 2^(n1). Then xxx will either be divisible by 2^n or leave a remainder of 2^(n1) when divided by 2^n.
Affixing a digit to the left of xxx will be a multiple of 10^(n1), and therefore of 2^(n1). If the previous string, with n1 digits, was already divisible by 2^n, then this digit will be an 8, and the added value will be divisible by 2^(n+2) and, a fortiori, by 2^n, and so also will be the total new value. If, however, the previous string left a remainder of 2^(n1) when divided by 2^n, the new digit will be a 9, and 9*10^(n1) will also leave a remainder of 2^(n1) when divided by 2^n, and so when added to the previous value, will complement it and the total value will be divisible by 2^n.
BTW, Ady, your sequence 8, 88, 988 etc. should be 8, 88, 888, 9888 etc.

Posted by Charlie
on 20111222 09:59:53 