En $k$ números consecutivos uno tiene suma de dígitos divisible por $11$

Question

Hallar el menor número entero positivo $k$ con la propiedad de que dado cualquier $k$ enteros positivos consecutivos, hay al menos uno cuya suma de dígitos es divisible por $11$ .

Puedo mostrar por $k\leq 57$ . Entre cualquier $29$ números enteros positivos consecutivos con la misma cifra de las centenas y cifras superiores, al menos uno tiene suma de cifras divisible por $11$ . Esto puede comprobarse mediante el trabajo de casos. Dado que nuestros enteros positivos consecutivos pueden abarcar dos centenas diferentes, tenemos $k\leq 29+28=57$ .

Por otra parte, entre las cifras $1,2,\ldots,28$ ninguno tiene suma de dígitos divisible por $11$ Así que $k\geq 29$ .

Answer 1

Esto es lo que ocurre con los números del intervalo $[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

y esto es lo que ocurre en la gama $[101,200]$ (sólo un $+1$ con respecto al cuadro anterior)

  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 

Entonces en el rango $[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  

Entonces en el rango $[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$ y así sucesivamente, hasta el rango $[1001,1100]$ .

No necesitamos más mesa. Al cruzar $100n$ siempre cambiamos entre dos de las tablas anteriores. Así que sólo tenemos que contar cuántos no ceros consecutivos hay, en la parte superior e inferior de cada tabla, y luego añadir un poco de trabajo manual. Podemos comprobar que si cruzamos un número de la forma $100 n$ no podemos tener más de $20+18$ números enteros consecutivos con la suma de dígitos $\not\equiv 0\pmod{11}$ . Lo que ocurre, por ejemplo, en la gama $[999981,1000018]$ .

En fin:

En $\color{red}{39}$ enteros positivos consecutivos, siempre hay un entero con la suma de dígitos $\equiv 0\pmod{11}$ .

Answer 2

Denote por $r(n)$ el resto módulo $11$ de la suma de dígitos decimales de $n$ . Un número $n$ es bien si $r(n)=0$ .

Reclamación: La diferencia $n'-n$ entre dos números buenos consecutivos $n$ , $n'$ es como máximo $39$ y este límite no puede mejorarse.

Prueba:

Las cifras $n:=999\,980$ et $n':=1\,000\,019$ son buenos números consecutivos con $n'-n=39$ .

Ahora viene lo esencial: Denotemos por $p(n)\geq0$ el número de nueves finales en la representación decimal de $n$ . Ejemplo: $p(4199)=2$ . Entonces tenemos la recursión $$r(n+1)=r(n)+1+2p(n)\qquad({\rm mod}\ 11)\ ,\tag{1}$$ porque en la transición $n\rightsquigarrow n+1$ les $p(n)$ los nueves finales se sustituyen por ceros y el dígito inmediatamente anterior se incrementa en $1$ .

Supongamos ahora que $n$ es un buen número. Escriba a $$n=n_0+j$$ con $n_0$ divisible por $10$ et $0\leq j\leq 9$ . Ponga $$n_k:=n_0+10k\qquad(k\geq1)\ .$$ Si $r(n_1)\ne1$ es decir, $r(n_1)\in\{0,2,3,4,5,6,7,8,9,10\}$ entonces hay un buen número $n'$ en la década que comienza con $n_1$ y $n'-n\leq19$ .

Si $r(n_1)=1$ pero $r(n_2)\ne1$ entonces hay un buen número $n'$ en la década que comienza con $n_2$ y $n'-n\leq29$ .

Queda por examinar el caso $r(n_1)=r(n_2)=1$ . La recursión $(1)$ implica $$10+2p(n_2-1)=0\qquad({\rm mod}\ 11)\ ,$$ o $p(n_2-1)=6\ ({\rm mod}\ 11)$ . En particular $p(n_2-1)\geq2$ y esto refuerza $p(n_3-1)=1$ . Utilización de $(1)$ de nuevo podemos concluir que $r(n_3)=2$ de donde $n':=n_3+9$ es bueno, con $n'-n\leq39$ .