Sum of Digits Divisible by 11

Date: 08/16/99 at 08:05:26
From: Anoop
Subject: Divisibility

Dear Sir,

I've been stuck on this question for days now. Prove that in a 
sequence of 39 consecutive natural numbers there exists at least one 
number such that the sum of its digits is divisible by 11.

Please help me out. Even my math teacher is stumped.
Anoop.

Date: 08/16/99 at 13:38:21
From: Doctor Rob
Subject: Re: Divisibility

Thanks for writing to Ask Dr. Math.

The digital sum of the successor of a natural number is 1 greater than 
the digital sum of the number, except when the number ends in 9. When 
a number ends in 9, the digital sum of its successor is 8 less than 
the digital sum of the number, except when the number ends in 99. When 
a number ends in 99, the digital sum of its successor is 17 less than 
the digital sum of the number, except when the number ends in 999.

The general rule is that if a number X ends with exactly N 9's, then 
the digital sum of X+1 minus the digital sum of X equals 1 - 9*N.

Suppose you did have 38 consecutive numbers A, A+1, ..., A+37 all of 
whose digital sums were not divisible by 11. Then you can prove that 
both A-1 and A+38 have digital sums divisible by 11, so there aren't 
39 numbers in a row with that property.

Start by realizing that if none of 38 consecutive numbers ends with 
99, then one of their digital sums must be divisible by 11, since 
starting with a number that ends in a 1, the pattern in digital sums 
goes:

                      Final Digit
    0    1    2    3    4    5    6    7    8    9
   -------------------------------------------------
        c  , c+1, c+2, c+3, c+4, c+5, c+6, c+7, c+8,
   c  , c+1, c+2, c+3, c+4, c+5, c+6, c+7, c+8, c+9,
   c+1, c+2, c+3, c+4, c+5, c+6, c+7, c+8, c+9, c+10,
   c+2, c+3, c+4, c+5, c+6, c+7, c+8, c+9, c+10,

So eleven consecutive values of the digital sum are covered by at 
least one of any 29 consecutive numbers, and one of those eleven 
consecutive values must be divisible by 11. Thus one of them must end 
in 99.

Next see that A+18 should be the number ending in 99.

Then see that it cannot end in exactly 2, 3, 4, or 5 nines, for a 
similar reason. (Make a similar chart for each.)

Finally, show that A+18 can end with exactly 6 nines, and must have 
digital sum of the form c = 11*k + 10.  Then A-1 and A+38 have digital 
sums 11*k and 11*(k-3), respectively.

- Doctor Rob, The Math Forum
  http://mathforum.org/dr.math/