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?
DEFDBL AZ
FOR n = 1 TO 99999999
s$ = LTRIM$(STR$(n))
sod = 0
FOR i = 1 TO LEN(s$)
sod = sod + VAL(MID$(s$, i, 1))
NEXT
IF sod MOD 11 = 0 THEN
IF gap > max THEN
max = gap
PRINT prev, n, gap
END IF
prev = n
gap = 0
ELSE
gap = gap + 1
END IF
NEXT
finds that 999980 and 1000019 are two consecutive occurrences of numbers whose sod is a multiple of 11, and there is a gap of 38 where the sod is not a multiple of 11, so one of these two has to be included to get the congruence, bringing the set's cardinality to 39.

Posted by Charlie
on 20120219 12:38:12 