Find a 13 digit positive integer N whose base ten representation consists entirely of 8s and 9s such that 2¹³ 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