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/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum