Question

¿Cuántos múltiplos enteros positivos de $1001$ se pueden expresar en la forma $10^{j} - 10^{i},$ donde $i$ y $j$ son enteros y $0 \le i \lt j \le 99$ ?

How many positive integer multiples of $1001$ can be expressed in the form $10^{j} - 10^{i},$ where $i$ and $j$ are integers and $0 \le i \lt j \le 99?$

Respuesta

Respuesta: 784

Conceptos:orden multiplicativo aritmética modular conteo de pares

Nivel de dificultad: 2710

Pista pequeña:

Factoriza $10^j - 10^i = 10^i(10^{j-i} - 1)$ y observa que $1001$ es coprimo con $10^i$ .

Factor $10^j - 10^i = 10^i(10^{j-i} - 1)$ and note that $1001$ is coprime to $10^i$

Pista grande:

$10^k - 1$ es divisible por $1001$ exactamente cuando $k$ es múltiplo de $6,$ así que cuenta los pares $0 \le i \lt j \le 99$ con $j - i$ múltiplo de $6$ .

$10^k - 1$ is divisible by $1001$ exactly when $k$ is a multiple of $6,$ so count pairs $0 \le i \lt j \le 99$ with $j - i$ a multiple of $6$

Solución:

Factoriza $10^j - 10^i = 10^i(10^{j-i} - 1).$ Como $1001 = 7 \cdot 11 \cdot 13$ es coprimo con $10^i,$ necesitamos que $10^{j-i} - 1$ sea divisible por $1001.$ El orden multiplicativo de $10$ es $6$ módulo $7,$ $2$ módulo $11,$ y $6$ módulo $13,$ así que $10^k \equiv 1 \pmod{1001}$ exactamente cuando $k$ es múltiplo de $6.$ Pares distintos $(i, j)$ dan valores distintos, así que basta con contar los pares.

Para $j - i = 6d$ con $1 \le d \le 16,$ el índice $i$ puede ser $0, 1, \ldots, 99 - 6d,$ lo que da $100 - 6d$ opciones. El total es $\begin{aligned} &\sum_{d=1}^{16} (100 - 6d) \\ &= 94 + 88 + \cdots + 4 \\ &= \frac{(94 + 4) \cdot 16}{2} \\ &= 784. \end{aligned}$

Factor $10^j - 10^i = 10^i(10^{j-i} - 1).$ Since $1001 = 7 \cdot 11 \cdot 13$ is coprime to $10^i,$ we need $10^{j-i} - 1$ to be divisible by $1001.$ The multiplicative order of $10$ is $6$ modulo $7,$ $2$ modulo $11,$ and $6$ modulo $13,$ so $10^k \equiv 1 \pmod{1001}$ exactly when $k$ is a multiple of $6.$ Distinct pairs $(i, j)$ give distinct values, so we just count the pairs.

For $j - i = 6d$ with $1 \le d \le 16,$ the index $i$ can be $0, 1, \ldots, 99 - 6d,$ giving $100 - 6d$ choices. The total is $\begin{aligned} &\sum_{d=1}^{16} (100 - 6d) \\ &= 94 + 88 + \cdots + 4 \\ &= \frac{(94 + 4) \cdot 16}{2} \\ &= 784. \end{aligned}$

2001 AIME II Problema 10

Respuesta: 784

Nivel de dificultad: 2710

Pista pequeña:

Pista grande:

Solución:

El Problema 10 en otros años