Question

Sea $\mathcal{S}$ el conjunto de enteros entre $1$ y $2^{40}$ cuyas expansiones binarias tienen exactamente dos $1$ . Si se elige un número al azar de $\mathcal{S},$ la probabilidad de que sea divisible por $9$ es $\frac{p}{q},$ donde $p$ y $q$ son enteros positivos primos entre sí. Halla $p + q.$

Let $\mathcal{S}$ be the set of integers between $1$ and $2^{40}$ whose binary expansions have exactly two $1$ 's. If a number is chosen at random from $\mathcal{S},$ the probability that it is divisible by $9$ is $\frac{p}{q},$ where $p$ and $q$ are relatively prime positive integers. Find $p + q.$

Respuesta

Solución:

El conjunto $\mathcal{S}$ consta de los $\binom{40}{2} = 780$ números $2^a + 2^b$ con $0 \le a \lt b \le 39.$ Como $2^a$ es coprimo con $9,$ tenemos $9 \mid 2^a(2^{b-a} + 1)$ exactamente cuando $2^{b-a} \equiv -1 \pmod{9}.$ Las potencias de $2$ módulo $9$ recorren $2, 4, 8, 7, 5, 1$ con periodo $6,$ así que $2^d \equiv 8 \equiv -1$ exactamente cuando $d \equiv 3 \pmod{6}.$

Para cada diferencia $d = b - a$ hay $40 - d$ pares, así que el número de múltiplos de $9$ en $\mathcal{S}$ es $\begin{aligned} &\sum_{d = 3, 9, \ldots, 39} (40 - d) \\ &= 37 + 31 + 25 \\ &\quad {}+ 19 + 13 + 7 + 1 \\ &= 133. \end{aligned}$

La probabilidad es $\frac{133}{780},$ y como $133 = 7 \cdot 19$ mientras que $780 = 2^2 \cdot 3 \cdot 5 \cdot 13,$ está en su forma más simple. Por tanto $p + q = 133 + 780 = 913.$

The set $\mathcal{S}$ consists of the $\binom{40}{2} = 780$ numbers $2^a + 2^b$ with $0 \le a \lt b \le 39.$ Since $2^a$ is coprime to $9,$ we have $9 \mid 2^a(2^{b-a} + 1)$ exactly when $2^{b-a} \equiv -1 \pmod{9}.$ The powers of $2$ modulo $9$ cycle through $2, 4, 8, 7, 5, 1$ with period $6,$ so $2^d \equiv 8 \equiv -1$ exactly when $d \equiv 3 \pmod{6}.$

For each difference $d = b - a$ there are $40 - d$ pairs, so the number of multiples of $9$ in $\mathcal{S}$ is $\begin{aligned} &\sum_{d = 3, 9, \ldots, 39} (40 - d) \\ &= 37 + 31 + 25 \\ &\quad {}+ 19 + 13 + 7 + 1 \\ &= 133. \end{aligned}$

The probability is $\frac{133}{780},$ and since $133 = 7 \cdot 19$ while $780 = 2^2 \cdot 3 \cdot 5 \cdot 13,$ it is in lowest terms. Thus $p + q = 133 + 780 = 913.$

2004 AIME II Problema 10

Solución:

El Problema 10 en otros años