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 A-Z
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 2012-02-19 12:38:12