Question

Para cada entero positivo $n,$ sea $a_n$ el menor múltiplo entero positivo de $23$ tal que $a_n \equiv 1 \pmod{2^n}.$ Halla el número de enteros positivos $n$ menores o iguales que $1000$ que satisfacen $a_n = a_{n+1}.$

For each positive integer $n$ let $a_n$ be the least positive integer multiple of $23$ such that $a_n \equiv 1 \pmod{2^n}.$ Find the number of positive integers $n$ less than or equal to $1000$ that satisfy $a_n = a_{n+1}.$

Respuesta

Solución:

Escribe $a_n = 23 b_n,$ donde $b_n$ es el único entero de $[1, 2^n]$ con $23 b_n \equiv 1 \pmod{2^n},$ es decir, el inverso de $23$ módulo $2^n.$ Reducir módulo $2^n$ muestra que $b_{n+1} \in \{b_n,\ b_n + 2^n\},$ así que $a_n = a_{n+1}$ exactamente cuando $b_{n+1} = b_n,$ lo que ocurre exactamente cuando el dígito binario de peso $2^n$ en $b_{n+1}$ es $0.$

Como $23 \cdot 89 = 2047 = 2^{11} - 1,$ poniendo $T_k = 1 + 2^{11} + 2^{22}$ ${}+ \cdots + 2^{11(k-1)}$ se obtiene $23 \cdot 89\,T_k = 2^{11k} - 1,$ así que $\begin{gathered} 23\left(2^{11k} - 89\,T_k\right) \\ \equiv 1 \pmod{2^{11k}}, \end{gathered}$ y todo $b_n$ con $n \le 11k$ es la reducción de $2^{11k} - 89\,T_k$ módulo $2^n.$ En binario, $89 = 1011001_{\text{two}}$ ocupa las posiciones $0, 3, 4, 6$ de cada bloque de $11$ bits de $89\,T_k.$ Como $89\,T_k$ es impar, $2^{11k} - 89\,T_k$ $= \bigl(2^{11k} - 1 - 89\,T_k\bigr) + 1$ mantiene el dígito $0$ igual a $1$ y complementa todos los dígitos en las posiciones $1$ hasta $11k - 1.$

Así que para $n \ge 1,$ el dígito de peso $2^n$ es $0$ exactamente cuando $n \equiv 0, 3, 4, 6 \pmod{11}.$ Entre $1 \le n \le 1000 = 90 \cdot 11 + 10,$ el residuo $0$ aparece $90$ veces y los residuos $3,$ $4,$ $6$ aparecen $91$ veces cada uno, para un total de $90 + 3 \cdot 91 = 363.$

Write $a_n = 23 b_n,$ where $b_n$ is the unique integer in $[1, 2^n]$ with $23 b_n \equiv 1 \pmod{2^n},$ i.e. the inverse of $23$ mod $2^n.$ Reducing mod $2^n$ shows $b_{n+1} \in \{b_n,\ b_n + 2^n\},$ so $a_n = a_{n+1}$ exactly when $b_{n+1} = b_n,$ which happens exactly when the binary digit of weight $2^n$ in $b_{n+1}$ is $0.$

Since $23 \cdot 89 = 2047 = 2^{11} - 1,$ setting $T_k = 1 + 2^{11} + 2^{22}$ ${}+ \cdots + 2^{11(k-1)}$ gives $23 \cdot 89\,T_k = 2^{11k} - 1,$ so $\begin{gathered} 23\left(2^{11k} - 89\,T_k\right) \\ \equiv 1 \pmod{2^{11k}}, \end{gathered}$ and every $b_n$ with $n \le 11k$ is the reduction of $2^{11k} - 89\,T_k$ mod $2^n.$ In binary, $89 = 1011001_{\text{two}}$ occupies positions $0, 3, 4, 6$ of each $11$ -bit block of $89\,T_k.$ Since $89\,T_k$ is odd, $2^{11k} - 89\,T_k$ $= \bigl(2^{11k} - 1 - 89\,T_k\bigr) + 1$ keeps digit $0$ equal to $1$ and complements every digit in positions $1$ through $11k - 1.$

So for $n \ge 1,$ the digit of weight $2^n$ is $0$ exactly when $n \equiv 0, 3, 4, 6 \pmod{11}.$ Among $1 \le n \le 1000 = 90 \cdot 11 + 10,$ the residue $0$ occurs $90$ times and the residues $3,$ $4,$ $6$ occur $91$ times each, for a total of $90 + 3 \cdot 91 = 363.$

2023 AIME II Problema 15

Solución:

El Problema 15 en otros años