Determine the total number of seven-digit base 10 positive integers divisible by 11 and having the sum of their digits equal to 59. (No computer programs)

For seven digits to sum to 59 they must be nearly all 9's.  Since 9*7=63 we must fall short by only 4.  That gives only a few sets of 7 digits to consider (ignoring order for now):
8888999
7889999
7799999
6899999
5999999

Now consider the divisibility by 11: the difference between the sum of the digits in the even places and the sum of the digits in the odd places must be divisible by 11.   Call these sums a and b.  So a+b=59 and a-b=0,11,22...

for a-b=0 they must be non-integers
for a-b=11 we have a=35, b=24
for a-b=22 or above a has to be too big

So we need to partition the digits of the original list into two groups whose sums are 24 and 35.  For four digits to sum to 35 you can only have three 9's and one 8.  Only three of the lists above can do that:
888 and 8999
789 and 8999
699 and 8999

Now be just have to count permutations of ways to riffle them together.
888 and 8999 gives 1*4 = 4 numbers
789 and 8999 gives 6*4 = 24 numbers
699 and 8999 gives 3*4 = 12 numbers
For a final solution of 40 numbers.

I won't list them all but the smallest and largest are
9999968 = 11*909088
8699999 = 11*790909

A very fun problem.

Posted by Jer on 2013-06-07 10:25:26