IBM Research Ponder This (Desafío de junio)

Question

Este fue el reto del mes pasado en "IBM Reseach Ponder This". No consigo entender la solución publicada. ¿Puede alguien explicarlo mejor?

Desafío

Encuentra un número racional (una fracción de dos enteros) que satisfaga las siguientes condiciones:

1)Su denominador tiene cinco dígitos y todos ellos son diferentes.

2)En la representación decimal infinita, cada dígito ocurre un número igual de veces en los dígitos desde mil millones hasta dos mil millones de lugares a la derecha del punto decimal (inclusive), excepto el último dígito del denominador, que ocurre dos veces más que los otros nueve dígitos.

3)Su numerador contiene el menor número posible de dígitos diferentes.

Actualización 6/4: Para aclarar el problema, he aquí un ejemplo: 5/17 = 0,294117647058823529411764705882... y en el dígito 11 en los lugares 20-30 después del punto decimal el dígito 7 (el último dígito del demonimador) aparece dos veces más que el dígito 4, pero no dos veces más que el dígito 9 (que no aparece allí en absoluto).

Solución

La forma de que un dígito aparezca el doble de veces que los otros nueve es establecer un período de 11 dígitos. Para ello, necesitamos que la fracción sea X/99999999999. La factorización del denominador nos lleva a 21649 como denominador, y mirando los posibles numeradores encontramos que 639/21649 resuelve las dos primeras condiciones. Para obtener un menor número de dígitos distintos, 646/21649 puede parecer la mejor solución (sólo hay dos dígitos distintos), pero utilizando fracciones impropias, podemos obtener la mejor solución: 333333/21649.

Answer 1

Un número con notación decimal $0.NPPPPPP...$ , donde $N$ y $P$ son grupos de dígitos, es de la forma $$\frac{N(10^R-1)+P10^{S+R}}{10^s(10^R-1)},$$ donde $S$ es la longitud de $N$ y $R$ es la longitud de $P$ .

En primer lugar, observe que para tener una expansión decimal de periodo $r$ el denominador tiene que ser un divisor de $10^S(10^r-1)$ . Dejemos que $x$ sea el número de veces que aparece un dígito diferente al último del denominador en el rango 1B a 2B de los primeros dígitos de la expansión decimal. Entonces ese dígito especial aparece $2x$ cada uno de los otros aparecen $x$ . Así que, $2x+x+x+x+x+x+x+x+x+x=2x+9x=11x=1B$ .

Creo que hicieron una conjetura, que tal vez también se pueda probar si se trabaja con cuidado, que como queremos un numerador pequeño también podemos querer un denominador pequeño, y luego un período pequeño. Entonces toman $11$ como el período, $N=S=0$ . Así que el denominador es un divisor de $10^{11}-1$ . Encuentran el único divisor de $10^{11}-1$ de $5$ dígitos y ningún dígito repetido. Es decir, que $21649$ . A continuación, busque un numerador (haga que el ordenador lo haga).

Por ejemplo, como no quieren dígitos repetidos en el denominador entonces el factor $10^S$ deben anularse, casi por completo. Así que el numerador debe ser divisible, al menos, por $10^{S-1}$ . Así que, $N$ debe ser divisible por $10^{S-1}$ .

Answer 2

Toda esta cuestión está fuertemente relacionada con una simple, pero profunda, observación: En una base determinada $b$ los números racionales de la forma $\frac{k}{b-1}$ tienen un "decimal" repetido en la base dada $b$ de longitud uno, y de hecho, para cada $k$ en $\{1,...,b-2\}$ que el número de esa cifra repetida es $k$ .

De forma más general, un decimal repetido de longitud $n$ (en base $b$ ) puede expresarse siempre como $k/(b^n-1)$ para algún número natural $0<k<b^n-1$ . Esto es una consecuencia del Pequeño Teorema de Fermat y una observación básica sobre el algoritmo de división estándar (adaptado a la base $b$ ).

Hice esta observación cuando estudiaba la pregunta "¿Cuánto dura la parte repetida de la expresión decimal de $1/n$ para cualquier $n$ (en base $10$ )" y lo generalizó rápidamente a una base arbitraria $b$ (es un resultado bastante conocido de la teoría elemental de los números, como resulta).