Combinatorics – Among $k$ Consecutive Numbers One Has Sum of Digits Divisible by $11$

combinatorics

Find the least positive integer $k$ with the property that given any $k$ consecutive positive integers, there is at least one whose sum of digits is divisible by $11$.

I can show for $k\leq 57$. Among any $29$ consecutive positive integers with the same hundreds' digit and higher digits, at least one has sum of digits divisible by $11$. This can be checked by casework. Since our consecutive positive integers may span two different hundreds' digits, we have $k\leq 29+28=57$.

On the other hand, among the numbers $1,2,\ldots,28$ none has sum of digits divisible by $11$, so $k\geq 29$.

Best Answer

This is what happens for the numbers in the range $[1,100]$:

  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  3
  4  5  6  7  8  9 10  0  1  4
  5  6  7  8  9 10  0  1  2  5
  6  7  8  9 10  0  1  2  3  6
  7  8  9 10  0  1  2  3  4  7
  8  9 10  0  1  2  3  4  5  8
  9 10  0  1  2  3  4  5  6  9
 10  0  1  2  3  4  5  6  7  1

and this what happens in the range $[101,200]$ (just a $+1$ with respect to the previous table)

  2  3  4  5  6  7  8  9 10  2
  3  4  5  6  7  8  9 10  0  3
  4  5  6  7  8  9 10  0  1  4
  5  6  7  8  9 10  0  1  2  5
  6  7  8  9 10  0  1  2  3  6
  7  8  9 10  0  1  2  3  4  7
  8  9 10  0  1  2  3  4  5  8
  9 10  0  1  2  3  4  5  6  9
 10  0  1  2  3  4  5  6  7 10
  0  1  2  3  4  5  6  7  8  2

Then in the range $[201,300]$:

  3  4  5  6  7  8  9 10  0  3
  4  5  6  7  8  9 10  0  1  4
  5  6  7  8  9 10  0  1  2  5
  6  7  8  9 10  0  1  2  3  6
  7  8  9 10  0  1  2  3  4  7
  8  9 10  0  1  2  3  4  5  8
  9 10  0  1  2  3  4  5  6  9
 10  0  1  2  3  4  5  6  7 10
  0  1  2  3  4  5  6  7  8  0
  1  2  3  4  5  6  7  8  9  3

Then in the range $[301,400]$:

  4  5  6  7  8  9 10  0  1  4  
  5  6  7  8  9 10  0  1  2  5         
  6  7  8  9 10  0  1  2  3  6
  7  8  9 10  0  1  2  3  4  7
  8  9 10  0  1  2  3  4  5  8
  9 10  0  1  2  3  4  5  6  9
 10  0  1  2  3  4  5  6  7 10 
  0  1  2  3  4  5  6  7  8  0  
  1  2  3  4  5  6  7  8  9  1    
  2  3  4  5  6  7  8  9 10  4

$\ldots$ and so on, till the range $[1001,1100]$.

We do not need any more table. When crossing $100n$, we always switch between two of the previous tables. So we just need to count how many consecutive non-zeroes are there, at the top and the bottom of every table, then add a little of handwork. We may check that if we cross a number of the form $100 n$, we cannot have more than $20+18$ consecutive integers with the digit sum $\not\equiv 0\pmod{11}$. Than happens, for instance, in the range $[999981,1000018]$.

Anyway:

Among $\color{red}{39}$ consecutive positive integers, there is always an integer with the digit sum $\equiv 0\pmod{11}$.

Related Question