Find a 13 digit positive integer N whose base ten representation consists entirely of 8s and 9s
such that 213 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 (n-1)-digit number divisible by 2^(n-1). Then xxx will either be divisible by 2^n or leave a remainder of 2^(n-1) when divided by 2^n.
Affixing a digit to the left of xxx will be a multiple of 10^(n-1), and therefore of 2^(n-1). If the previous string, with n-1 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^(n-1) when divided by 2^n, the new digit will be a 9, and 9*10^(n-1) will also leave a remainder of 2^(n-1) 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 2011-12-22 09:59:53