Dado un entero x (base 10), ¿cómo encontramos el menor entero y (base 10), de modo que y solo consista en los dígitos 0 y 1, y y es divisible por x? Además, ¿cómo hacemos para demostrar que siempre existe ay con las condiciones mencionadas anteriormente?

Answer 1

Sridhar ha explicado por qué [math] y [/ math] debe existir, así que aquí hay una manera de encontrar el más pequeño. Buscamos [math] f (0, x) [/ math], donde [math] f (k, x) [/ math] es el entero positivo más pequeño [math] y [/ math] que consiste en 0 y 1 tal que [math] y \ equiv k \ pmod x [/ math], para todos [math] 0 \ le k <x [/ math]. Si [matemática] k = 1 [/ matemática] o [matemática] x = 1 [/ matemática], entonces [matemática] f (k, x) = 1 [/ matemática]. De lo contrario, [math] f (k, x) = 10n + b [/ math], donde [math] n [/ math] es otro entero positivo que consiste en 0 y 1, y [math] b \ in \ {0, 1 \} [/ matemáticas]. Deje [math] d = \ gcd \ {10, x \} [/ math]. Entonces debemos tener [math] b \ equiv k \ pmod d [/ math], y
[matemáticas] 10n \ equiv k – b \ pmod x \ iff [/ matemáticas]
[matemáticas] \ frac {10} {d} n \ equiv \ frac {k – b} {d} \ pmod {\ frac xd} \ iff [/ matemáticas]
[matemática] n \ equiv \ izquierda (\ frac {10} {d} \ derecha) ^ {- 1} \ frac {k – b} {d} \ pmod {\ frac xd} [/ matemática].
Por lo tanto,
[matemáticas] f (k, x) = \ min_b 10f \ left (\ left (\ frac {10} {d} \ right) ^ {- 1} \ frac {k – b} {d} \ bmod \ frac xd , \ frac xd \ right) [/ math] [math] {} + b [/ math].
Si construimos un árbol de búsqueda con bordes de [math] (k, x) [/ math] a [math] \ bigl (\ bigl (\ tfrac {10} {d} \ bigr) ^ {- 1} \ tfrac { k – b} {d} \ bmod \ tfrac xd, \ tfrac xd \ bigr) [/ math], habrá un número finito (de hecho, como máximo [math] O (x) [/ math]) total de nodos distintos . Podemos usar una versión de búsqueda de amplitud para encontrar la ruta óptima desde [matemática] (0, x) [/ matemática] a [matemática] (1,?) [/ Matemática] o [matemática] (?, 1) [/matemáticas].

La secuencia de respuestas es A004290.

Answer 2

Prueba de que existe al menos una de estas formas: considere la secuencia cero, luego 1, luego 11, luego 111, luego 1111, etc. Dado que hay infinitos elementos en esta secuencia, pero solo finitamente muchos restos módulo x, debemos En algún momento encontramos dos miembros de esta secuencia con el mismo módulo restante x. La diferencia de esos dos miembros será divisible por x, y consistirá en una cadena de 1s seguida de una cadena de 0s. QED