Question

Sea $S$ el conjunto de todos los números racionales que pueden expresarse como un decimal periódico de la forma $0.\overline{abcd},$ donde al menos uno de los dígitos $a,$ $b,$ $c,$ o $d$ es distinto de cero. Sea $N$ el número de numeradores distintos que se obtienen cuando los números de $S$ se escriben como fracciones en su mínima expresión. Por ejemplo, tanto $4$ como $410$ se cuentan entre los numeradores distintos de los números de $S$ porque $0.\overline{3636} = \frac{4}{11}$ y $0.\overline{1230} = \frac{410}{3333}.$ Halla el residuo cuando $N$ se divide entre $1000.$

Let $S$ be the set of all rational numbers that can be expressed as a repeating decimal in the form $0.\overline{abcd},$ where at least one of the digits $a,$ $b,$ $c,$ or $d$ is nonzero. Let $N$ be the number of distinct numerators obtained when numbers in $S$ are written as fractions in lowest terms. For example, both $4$ and $410$ are counted among the distinct numerators for numbers in $S$ because $0.\overline{3636} = \frac{4}{11}$ and $0.\overline{1230} = \frac{410}{3333}.$ Find the remainder when $N$ is divided by $1000.$

Respuesta

Solución:

Cada elemento de $S$ es igual a $\frac{k}{9999}$ para algún $1 \le k \le 9999,$ donde $9999 = 3^2 \cdot 11 \cdot 101.$ En su mínima expresión esto es $\frac{m}{D}$ donde $D \mid 9999,$ $m \le D,$ y $\gcd(m, D) = 1;$ recíprocamente, cualquier $\frac{m}{D}$ de este tipo surge de $k = m \cdot \frac{9999}{D}.$ Así que $N$ cuenta los enteros $m$ que son a lo sumo, y coprimos con, algún divisor $D$ de $9999.$

Clasifica $m$ según cuáles de los primos $3, 11, 101$ lo dividen, usando siempre el mayor divisor $D$ coprimo con $m.$ Si $\gcd(m, 9999) = 1,$ toma $D = 9999:$ hay $\varphi(9999) = 6000$ tales $m.$ Si solo $3 \mid m,$ toma $D = 11 \cdot 101 = 1111:$ los múltiplos de $3$ hasta $1111$ que evitan $11$ y $101$ suman $370 - 33 - 3 = 334.$ Si solo $11 \mid m,$ toma $D = 9 \cdot 101 = 909:$ eso da $82 - 27 = 55.$ Si solo $101 \mid m,$ entonces $D = 99 \lt 101$ no admite ninguno. Si $33 \mid m$ pero $101 \nmid m,$ toma $D = 101:$ los valores $33, 66, 99$ dan $3$ más, y cualquier $m$ divisible por $3 \cdot 101$ o $11 \cdot 101$ necesitaría $D \le 11,$ lo cual es imposible.

Por lo tanto $N = 6000 + 334 + 55 + 3$ $= 6392,$ y el residuo módulo $1000$ es $392.$

Every element of $S$ equals $\frac{k}{9999}$ for some $1 \le k \le 9999,$ where $9999 = 3^2 \cdot 11 \cdot 101.$ In lowest terms this is $\frac{m}{D}$ where $D \mid 9999,$ $m \le D,$ and $\gcd(m, D) = 1;$ conversely any such $\frac{m}{D}$ arises from $k = m \cdot \frac{9999}{D}.$ So $N$ counts the integers $m$ that are at most, and coprime to, some divisor $D$ of $9999.$

Classify $m$ by which of the primes $3, 11, 101$ divide it, always using the largest divisor $D$ coprime to $m.$ If $\gcd(m, 9999) = 1,$ take $D = 9999:$ there are $\varphi(9999) = 6000$ such $m.$ If $3 \mid m$ only, take $D = 11 \cdot 101 = 1111:$ multiples of $3$ up to $1111$ avoiding $11$ and $101$ number $370 - 33 - 3 = 334.$ If $11 \mid m$ only, take $D = 9 \cdot 101 = 909:$ that gives $82 - 27 = 55.$ If $101 \mid m$ only, then $D = 99 \lt 101$ admits none. If $33 \mid m$ but $101 \nmid m,$ take $D = 101:$ the values $33, 66, 99$ give $3$ more, and any $m$ divisible by $3 \cdot 101$ or $11 \cdot 101$ would need $D \le 11,$ which is impossible.

Therefore $N = 6000 + 334 + 55 + 3$ $= 6392,$ and the remainder modulo $1000$ is $392.$

2022 AIME I Problema 13

Solución:

El Problema 13 en otros años