Among $k$ consecutive numbers one has sum of digits divisible by $11$

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$.

Solutions Collecting From Web of "Among $k$ consecutive numbers one has sum of digits divisible by $11$"

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}$.

Denote by $r(n)$ the remainder modulo $11$ of the decimal digit sum of $n$. A number $n$ is good, if $r(n)=0$.

Claim: The difference $n’-n$ between two consecutive good numbers $n$, $n’$ is at most $39$, and this bound cannot be improved.

Proof:

The numbers $n:=999\,980$ and $n’:=1\,000\,019$ are consecutive good numbers with $n’-n=39$.

Now for the essential part: Denote by $p(n)\geq0$ the number of trailing nines in the decimal representation of $n$. Example: $p(4199)=2$. Then we have the recursion
$$r(n+1)=r(n)+1+2p(n)\qquad({\rm mod}\ 11)\ ,\tag{1}$$
because in the transition $n\rightsquigarrow n+1$ the $p(n)$ trailing nines are replaced by zeros, and the immediately preceding digit is increased by $1$.

Assume now that $n$ is a good number. Write $$n=n_0+j$$ with $n_0$ divisible by $10$ and $0\leq j\leq 9$. Put $$n_k:=n_0+10k\qquad(k\geq1)\ .$$
If $r(n_1)\ne1$, i.e., $r(n_1)\in\{0,2,3,4,5,6,7,8,9,10\}$, then there is a good number $n’$ in the decade beginning with $n_1$, and $n’-n\leq19$.

If $r(n_1)=1$, but $r(n_2)\ne1$, then there is a good number $n’$ in the decade beginning with $n_2$, and $n’-n\leq29$.

It remains to consider the case $r(n_1)=r(n_2)=1$. The recursion $(1)$ then implies
$$10+2p(n_2-1)=0\qquad({\rm mod}\ 11)\ ,$$
or $p(n_2-1)=6\ ({\rm mod}\ 11)$. In particular $p(n_2-1)\geq2$, and this enforces $p(n_3-1)=1$. Using $(1)$ again we can conclude that $r(n_3)=2$, whence $n’:=n_3+9$ is good, with $n’-n\leq39$.