Prove that within any 39 consecutive natural numbers there must exist at least one number with the sum of its digits divisible by 11.
Bonus: Can the bound (39) be lowered?

The normal rule (rule of 1) is that consecutive numbers clock forward one at a time, with their SOD covering the numbers 0 to 10 mod 11 consecutively. So if we start with a number, divisible by 10, whose SOD is 2 or more, mod 11, one of the numbers in the following decade will have a SOD divisible by 11.

But every tenth number clocks back 8 (rule of -8) when the decimal digit xxx9 turns into xx(x+1)0. So if we start with a number whose SOD is divisible by 11, and which ends in {00,10,20,30,40,50,60,70}, it will be followed by a sequence of 28 consecutive numbers whose SOD is not so divisible: {0,1,2,3,4,5,6,7,8,9,1,2,3,4,5,6,7,8,9,10,2,3,4,5,6,7,8,9,10,0}

This length can be improved upon if, after deploying the first rule of 8, we reach, say, 1000000 at the end of the second decade, since SOD 999999= 54=10 mod 11, and 1000000 = 1 mod 11 (rule of -9). Naturally, it is only possible to use this rule once!

Such a number is followed by 38 consecutive numbers whose SOD is not divisible by 11. So the bound is fixed and cannot be lowered.

There are 11 'power of 10 rules' in all {rules of -8,-6,-4,-2,0,-9,-7,-5,-3,-1}  after which the list repeats.

For obvious reasons, none of the rules other than the rule of -8 and the rule of -9 can 'work', although, say,  the 'rule of -17' , 17 consecutive 9's turning into  100,000,000,000,000,000 would work just as well.

Edited on February 20, 2012, 2:59 am

Posted by broll on 2012-02-20 02:00:25