Encuentre el$n \ge 1000$ más pequeño, la suma$ 1+11+111+⋯+11⋯11 (n$ dígitos es divisible por$101$

Question

Tengo otra formación de problema, para un rumano de 6º grado de la competencia, para la cual no tengo respuesta. Encontrar el más pequeño de $n \ge 1000$ tal la suma de $ 1+11+111+⋯+11⋯11 (n digits)$ es divisible por 101. Estoy familiarizado con la suma, sé cómo calcular, pero puedo ver cómo me puede razonar acerca de la divisibilidad por $101$.

Hice un análisis numérico en ella, y parece que la solución es $n=1121$, mientras que los primeros números para los que la suma es divisible por 101 $110,313, 403, 404, 514, 717, 807,808, 918$ . También me di cuenta de que $1111$ es divisible por $101$, y también he visto que el patrón de $123456790$ se repite en la suma.

Answer 1

Desde $111100\ldots00$ es divisible por $101$, repetidamente puede quitar los cuatro principales $1$'s de $111\ldots 111$ hasta llegar a uno de $0,1,11,$ o $111$. Y usted puede reducir el $111$ a $10$. Así se obtiene la suma $$1+11+10+0+1+11+10+0+\ldots$$

mod $101$. Se puede tomar desde allí?

Answer 2

En primer lugar vamos a encontrar $F(n) = 1+11+111+...+\frac{10^n-1}{9}$.

$F(n) = \sum_{i=1}^n\frac{10^i-1}{9} = \frac{1}{9}(\sum_{i=1}^{n}10^i-\sum_{i=1}^n1) = \frac{10}{9}\frac{10^n-1}{9}-\frac{n}{9}=\frac{10^{n+1}-9n-10}{81}$

$101 | F(n) \implies 101 | (10^{n+1}-9n-10)$ como mcd(101, 81) = 1

$10^{n+1} \equiv 9n+10 \mod{101}$

Aviso

$10^{n+1} \equiv 10, -1, 91(-10), 1 \mod{101} \textrm{ when }n \equiv 0, 1, 2, 3 \mod{4}$ respectivamente.

En primer lugar, $9^{-1} \equiv 45\mod{101}$

Considere los casos:

$n \equiv 0 \mod{4}, 9n+10\equiv10,n\equiv0 \mod{101} \implies n \equiv 0 \mod{404}$

$n \equiv 1 \mod{4}, 9n+10\equiv-1,9n\equiv-11,n \equiv(45)(-11)\equiv-495\equiv10\mod{101}\implies n\equiv313\mod{404}$

Similar para los otros 2 casos, $n\equiv0, 110, 313, 403 \mod {404}$

$n = 0, 110, 313, 403, ..., 808, 918, 1121, ...$ así 1121 es el entero más pequeño >=1000.

Answer 3

Trabajo $\pmod {101}$ vemos que el resto de los sumandos son periódicas con el ciclo de $\{1,11,10,0\}$.

Queremos que la suma de los restos para ser un múltiplo de $101$.

Podemos conseguir $101$? Bien $1+11+10=22$. Para llegar a un múltiplo de $101$ vamos a tener que ir a través del ciclo de un número de veces y, a continuación, agregue $0$, $1$ o $12$. Por lo tanto buscamos $k$ tal que $$22k\equiv 0,-1,\, \text {or }\,-12 \pmod {101}$$

Es claro que la solución menos para $0$ es $101$.

Por fuerza bruta (aunque se podría usar el algoritmo de euclides):

La solución menos para $-1$ es $78$.

La solución menos para $-12$ es $27$.

Comenzando con los múltiplos $101$, vemos que la primera solución sería la $1212$.

Ahora teniendo en cuenta $78$, se nota que $78\times 4 = 312$, $(78+101)\times 4=716$, $78+2\times 101=1120$. Como $1120+1=1121<1212$, que el primer contendiente por ahora.

Necesitamos comprobar que no obtenemos un valor menor si partimos de $27$. Pero $27\times 4=108$, y la adición de $4\times 101=404$ a que en repetidas ocasiones el primer valor de $≥1000$ nos vienen a la es $1320$ por lo que no es bueno. (para ser cuidado, el anterior valor de $916$ y la adición de dos que no se a $1000$).

Por lo tanto podemos confirmar su resultado, $1121$ es óptimo.

Answer 4

Si se consideran los restos al dividir cada término por $101$ obtenemos la siguiente secuencia:

$$1 \equiv 1 \pmod {101}$$ $$11 \equiv 11 \pmod {101}$$ $$111 \equiv 10 \pmod {101}$$ $$1111 \equiv 0 \pmod {101}$$ $$11111 \equiv 1 \pmod {101}$$ $$ \cdots$$

No es difícil concluir que la los restos de repetición de cada una de las $4$ términos. También tenga en cuenta que cualquier suma de $4$ consecutivo términos se han resto $1+11+10+0 = 22$ al momento de la división por $101$. Por lo tanto:

$$\sum_{i=1}^{1000} a_n \equiv 22\cdot 250 \equiv 46 \pmod{101}$$

donde $a_n = 11 \cdots 1 (n$ dígitos ). Ahora quiere resolver las siguientes ecuaciones:

$$46 + 22k_1 \equiv 100 \pmod{101}$$ $$46 + 22k_2 \equiv 89 \pmod {101}$$ $$46 + 22k_3 \equiv 0 \pmod {101}$$

El primero proviene de la adición de $k_1$ bloques de $4$ términos y la adición de sólo uno más después de llevar el resto a $0$. La segunda, viene de ading $k_2$ bloques de $4$ términos y la adición de los próximos dos después. La última ecuación se plantea como una de las formas para alcanzar resto $0$ es seguir sumando $k_3$ bloques de $4$ términos y los próximos tres después.

Deje $k_1,k_2,k_3$ ser el menos nonegative soluciones de la congruencia de las relaciones. Luego tenemos a $n_1 = (250+k_1)\cdot 4 + 1$, $n_2 = (250+k_2)\cdot 4 + 2$, $n_3 = (250+k_3)\cdot 4 + 3$. El entero más pequeño de $n_1,n_2,n_3$ es la querían $n$.

Answer 5

Denotar $1_n$ por el número de con $n$ dígitos, cada uno igual a $1$. E. g. $1_3 = 111$.

Empezar con mirar los restos de al $1_n$ se divide por $101$. Tenga en cuenta que $1_n = 10 \times 1_{n-1} + 1$, e $1_1 = 1$. Por lo tanto, de forma inductiva tenemos que la secuencia de $1_n \mod 101$(para $n \geq 1$) se parece a $$1,11,10,0,1,11,10,0,...$$

Ahora, vamos a denotar $b_m = \sum_{n=1}^m 1_n$. Estamos interesados en $b_m \mod 101$. Para ello, vamos a romper $m = 4k,4k+1,4k+2,4k+3$.

Para $m = 4k$, claramente $b_m \pmod{101} = 22k$. Para $m = 4k+1$ es $22k+1$, $m = 4k+2$ es $22k+12$, $m = 4k+3$ es $22k + 22$.

Por lo tanto, tenemos que resolver estas ecuaciones : $$ 22k \equiv 0 \pmod{101} \\ 22k+1 \equiv 0 \pmod{101} \\ 22k+12 \equiv 0 \pmod{101} \\ 22(k+1) \equiv 0 \pmod{101} $$

Cada uno de estos puede ser resuelto, ya que $22$ e $23$ son invertible mod $101$. La primera y la cuarta de estas ecuaciones tienen soluciones obvias. Yo de la lista de las soluciones correspondientes a continuación. $$ k \equiv 0 \mod 101 k \equiv 78 \mod 101 k \equiv 27 \mod 101 k \equiv -1 \mod 101 $$

Por lo tanto, las soluciones correspondientes a $b_m = 0$ son(para cada una de las $l \geq 0$) : $$ 4(101l) = 404l \\ 4(101l+78) + 1 = 404l + 313 \\ 4(101l+27) +2 = 404l+110 \\ 4(101l-1) + 3 = 404l-1 $$

Ahora, tenemos que combinar todo esto en cualquier solución de la forma $404l + d$ donde $l \geq 0$ e $d \in \{0,(-1=) 403,110,313\}$.

Por último, es fácil ver que $404 \times 2 + 313 = 1121$ es el más pequeño de la solución con cuatro dígitos.

---

Siento la necesidad de agregar a esto, pero creo que va a ser bonito de ver.

Deje que nos reemplace $101$ por un entero $N$ que es coprime a $2$ e $5$. El uso de la caja argumento para mostrar que el $N$ es divisible por $1_m$ para algunos $1 \leq m \leq n+1$. (Sugerencia : considere los restos al $1_m$ se divide por $n$).

Elegir el más pequeño $M$ tal que $N$ divide $1_M$. Entonces, ahora podemos ver en la secuencia de números de $b_m = \sum_{i=1}^m 1_n$, y pregunte: ¿existe un número $F$ tal que $b_F$ es un múltiplo de a$N$?

De hecho, no hay! Para ver esto, observe que $1_M$ es un múltiplo de a$N$. Supongamos que $b_M$ deja un resto $r$ mod $N$.

Reclamamos el siguiente inductivo fórmula se tiene: $$ b_{kM} = b_M\left(\frac{10^{kM}-1}{10^M - 1}\right) + \sum_{i=1}^{k-1} 1_{iM} $$

Esto se puede verificar fácilmente. Siguiente, tomando los restos modulo $N$ anterior, tenga en cuenta que $1_{iM}$ es un múltiplo de a$n$ desde $1_M$ es un múltiplo de a$n$. Así, podemos obtener : $$ b_{kM} \equiv r\times \left(\frac{10^{kM-1}}{10^M-1}\right) \pmod{N} $$

Observar que $\frac{10^{kM} - 1}{10^M-1} = \frac{1_{kM}}{1_M} = c_k$ .Tenga en cuenta que este es un número entero.

Reclamo : no existe $1 \leq K \leq N+1$ tal que $N$ divide $c_K$.

Para esto, el uso de encasillar en los restos de la $c_K$ mod $N$. Tenga en cuenta que dos de $c_1,...,c_{N+1}$ tienen el mismo resto mod $N$, decir $c_{s} > c_{t}$. A continuación, $N | c_s - c_t = 10^{t}(c_{s-t})$ (usted puede verificar esto). Pero $N$ es coprime a $10^r$, por lo tanto $N | c_{s-t}$. Tome $K = s-t$.

Por lo tanto, $b_{KM} \equiv rc_K \equiv 0 \mod N$.

Ahora, podemos encontrar infinidad de $F$ tal que $b_F$ es un múltiplo de a$N$, tomando $b_{2F},b_{3F}$ y así sucesivamente.

EN el ejemplo de $101$, se puede comprobar que $M = 4$ e $K = 101$ trabajado.