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

Respuesta: 392

Conceptos:decimal periódico Función φ de Euler análisis por casos

Nivel de dificultad: 3160

Pista pequeña:

Cada elemento de $S$ es $\frac{k}{9999}$ con $1 \le k \le 9999$ y $9999 = 3^2 \cdot 11 \cdot 101$

Every element of $S$ is $\frac{k}{9999}$ with $1 \le k \le 9999$ and $9999 = 3^2 \cdot 11 \cdot 101$

Pista grande:

$m$ es un numerador exactamente cuando $m \le D$ y $\gcd(m, D) = 1$ para algún divisor $D$ de $9999.$ Clasifica $m$ según cuáles de $3,$ $11,$ o $101$ lo dividen.

$m$ is a numerator exactly when $m \le D$ and $\gcd(m, D) = 1$ for some divisor $D$ of $9999.$ Classify $m$ by which of $3,$ $11,$ or $101$ divide it.

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$ divide a $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,$ o $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$ divide a $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$ divide a $m,$ toma $D = 9 \cdot 101 = 909:$ eso da $82 - 27 = 55.$ Si solo $101$ divide a $m,$ entonces $D = 99 \lt 101$ no admite ninguno. Si $m$ es divisible por $33$ pero no por $101,$ toma $D = 101:$ los valores $33,$ $66,$ y $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$ divides $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,$ or $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 only $3$ divides $m,$ take $D = 11 \cdot 101 = 1111:$ multiples of $3$ up to $1111$ avoiding $11$ and $101$ number $370 - 33 - 3 = 334.$ If only $11$ divides $m,$ take $D = 9 \cdot 101 = 909:$ that gives $82 - 27 = 55.$ If only $101$ divides $m,$ then $D = 99 \lt 101$ admits none. If $m$ is divisible by $33$ but not by $101,$ take $D = 101:$ the values $33,$ $66,$ and $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

Respuesta: 392

Nivel de dificultad: 3160

Pista pequeña:

Pista grande:

Solución:

El Problema 13 en otros años