Aumentar el número de dígitos distintos de cero (de AOPS)

Question

Encontré este problema actualmente sin resolver en el sitio de AOPS ( enlace ):

Permita que$n$ sea un entero positivo con exactamente$d$% dígitos que no sean cero. Muestre que hay un múltiplo de$n$ que tiene exactamente$d+1$% dígitos que no son cero.

Parece ser bastante desafiante y no tengo idea de cómo resolverlo. ¿Alguna pista sobre cómo proceder?

Answer 1

Usted puede combinar las tres sencillos trucos para resolver el problema:

1. Tomar un dígito mayor que $1$, y que se dividió en dos dígitos distintos de cero mediante la adición de $10^t-10^s$.

2. Si cada dígito en el número de $n$ $0$ o $1$, reemplace$n$$2n$.

3. Con el fin de deshacerse de los factores primos $2$$5$, multiplicar $n$ por una potencia de $10$.

---

Si $n$ tiene un dígito mayor que $1$ a continuación, vamos a $m=n$. De lo contrario, si cada dígito de $n$ $0$ o $1$ a continuación, vamos a $m=2n$. Por lo tanto $m$ es un múltiplo de a $n$, tiene el mismo valor distinto de cero dígitos como $n$, e $m$ tiene al menos un dígito mayor que $1$.

Deje $m=\sum_{i=0}^{k-1} a_i\cdot 10^i$ donde $a_0,\ldots,a_{k-1}$ son los dígitos decimales de $m$ y deje $g$ ser un índice con $a_g\ge2$.

Tomar dos enteros $t,s$ tal que $s>g$, $t>s+k$ y $10^t\equiv 10^s\pmod{n}$, y elegir $$ M = 10^{s-g}m + (10^t-10^s). $$ El factor de $10^{s-g}$ cambia el dígito $a_g$ $s$th posición. El plazo $10^t-10^s$ reemplaza el dígito $a_g$ $a_g-1$ (que es distinto de cero), y se agrega un nuevo primer dígito $1$. Debido a $t-s>k$, lo que provoca $1$ no se agrega a la anterior dígitos distintos de cero.