Buscando una explicación: Principio de encasillamiento-Demuestra que en una secuencia hay un número divisible por otro número

Question

¿Podría alguien dar una explicación a este problema? Tengo la respuesta, pero no entiendo el razonamiento que hay detrás.

P: Entre la secuencia $3, 33, 333, 3333,\dots$ demostrar que hay un número divisible por $1001$ (utilice el principio del encasillamiento).

A:

División por $1001 \Rightarrow$ (Usar PP), existe $2$ números en la secuencia, digamos $a_i$ y $a_j$ ( $1 \le i < j$ ) con el mismo resto

$a_{j-i}-10^i$

$a_j - a_i = a_{j-i}10^i$ es divisible por $1001$

$(1001, 10) = 1$ , relativamente primo

$\Rightarrow a_{j-i}$ es divisible por $1001$

Answer 1

Si dejas que $r_i$ sea el resto cuando $a_i$ se divide por $1001$ se obtiene una secuencia infinita de restos, $\langle r_1,r_2,r_3\dots\rangle$ . Considere la primera $1002$ de estos restos: cada uno de ellos tiene que ser uno de los enteros $0,1,2,\dots,1000$ y sólo hay $1001$ de estos posibles valores. Así, unos dos de los primeros $1002$ los restos deben ser iguales. Llamémoslos $r_i$ y $r_j$ , donde $1 \le i < j \le 1002$ .

Dejemos que $q_i$ sea el cociente cuando $a_i$ se divide por $1001$ Entonces $a_i = 1001q_i + r_i$ . Del mismo modo, si $q_j$ es el cociente cuando $a_j$ se divide por $1001$ entonces $a_j = 1001q_j + r_j$ . De ello se desprende que $$\begin{align*} a_j - a_i &= (1001q_j+r_j) - (1001q_i+r_i)\\ &= 1001(q_j-q_i)+(r_j-r_i)\\ &= 1001(q_j-q_i), \end{align*}$$

donde el último paso se justifica porque $r_j=r_i$ . Esto demuestra que $a_j-a_i$ es un múltiplo de $1001$ .

Ahora $a_j$ es una cadena de $j$ $3$ 's, y $a_i$ es una cadena de $i$ $3$ 's, así que $a_j-a_i$ es una cadena de $j-i$ $3$ seguido de $i$ $0$ 's. (Si no está seguro de esto, mire algunos ejemplos.) Y $a_{j-i}$ es una cadena de $j-i$ $3$ 's, así que $a_j-a_i$ es $a_{j-i}$ seguido de $i$ $0$ 's. Cada uno de esos $i$ $0$ representa una multiplicación por $10$ Así que $a_j-a_i = a_{j-i}10^i$ . Así, $a_{j-i}10^i$ es un múltiplo de $1001$ o, de forma más concisa, $1001\mid a_{j-i}10^i$ .

Finalmente, se tiene un teorema que dice que si $a\mid bc$ y $a$ y $b$ son relativamente primos, entonces $a\mid c$ . $1001$ y $10^i$ son relativamente primos, por lo que el teorema nos dice que $1001 \mid a_{j-i}$ es decir, que $a_{j-i}$ es un múltiplo de $1001$ .

Answer 2

Sugerencia $\rm\ \ x\overset{f}\mapsto 10\, x + 3\pmod{ 1001}\ $ tiene una órbita $\rm\ 0\overset{f}\mapsto3\overset{f}\mapsto33\overset{f}\mapsto 333\,\ldots\,$ que debe volver al ciclo de $\:0\:$ porque $\,f\,$ es invertible - con el inverso $\rm\:x\mapsto (x-3)/10\equiv 100\ (3-x)\:;\: $ es decir, ser un mapa invertible sobre un conjunto finito, $\,f\,$ es una permutación, cuyas órbitas son ciclos . Cada vez que la secuencia vuelve a cero se obtiene un elemento de la secuencia $\equiv 0,\:$ es decir, divisible por $1001.\,$ Así que hay infinitos elementos de este tipo. Aunque no es necesario, nótese que la órbita de $\:0\:$ es un ciclo de longitud $6,\,(0,\ 3,\ 33,\ 333,\ 330,\ 300),\,$ por lo que cada $6$ es divisible por $1001$ .

Nota: $\ $ Este cíclico La estructura de las órbitas de permutación es un hecho fundamental con amplias aplicaciones. Con frecuencia se pasa por alto esta sencilla estructura, lo que da lugar a argumentos ofuscados que equivalen esencialmente a reinventar la rueda / ciclo.