Question

Sea $x_0,$ $x_1,$ $x_2,$ $\ldots$ una sucesión de números, donde cada $x_k$ es $0$ o $1.$ Para cada entero positivo $n,$ define $S_n = \sum_{k=0}^{n-1} x_k 2^k.$ Supón que $7 S_n \equiv 1 \pmod{2^n}$ para todo $n \ge 1.$ ¿Cuál es el valor de la suma $x_{2019} + 2x_{2020} + 4x_{2021} + 8x_{2022}?$

Let $x_0,$ $x_1,$ $x_2,$ $\ldots$ be a sequence of numbers, where each $x_k$ is either $0$ or $1.$ For each positive integer $n,$ define $S_n = \sum_{k=0}^{n-1} x_k 2^k.$ Suppose $7 S_n \equiv 1 \pmod{2^n}$ for all $n \ge 1.$ What is the value of the sum $x_{2019} + 2x_{2020} + 4x_{2021} + 8x_{2022}?$

$6$

$7$

$12$

$14$

$15$

Respuesta: A

Conceptos:aritmética modular base numérica reconocimiento de patrones

Nivel de dificultad: 2270

Pista pequeña:

$S_n$ es el número formado por los $n$ bits bajos; la condición dice $S_n \equiv 7^{-1} \pmod{2^n}$ .

$S_n$ is the number formed by the low $n$ bits; the condition says $S_n \equiv 7^{-1} \pmod{2^n}$

Pista grande:

Así, los bits $x_k$ son los dígitos binarios (2-ádicos) de $\tfrac17;$ halla su patrón periódico.

So the bits $x_k$ are the binary (2-adic) digits of $\tfrac17;$ find their repeating pattern

Solución:

Como $S_n$ es el entero formado por los $n$ bits bajos, la condición $7S_n \equiv 1$ significa $S_n \equiv 7^{-1} \pmod{2^n}$ para todo $n.$ Así, los dígitos $x_k$ son los dígitos en base $2$ de $\tfrac17$ como número $2$ -ádico.

La división larga en base $2$ da los dígitos $x_0 = x_1 = x_2 = 1,$ y a partir de ahí el bloque se repite con periodo $3:$ para $k \ge 1,$ $x_k = 0$ exactamente cuando $k$ es divisible por $3,$ y $x_k = 1$ en caso contrario.

Como $2019$ y $2022$ son ambos divisibles por $3,$ mientras que $2020 \equiv 1$ y $2021 \equiv 2 \pmod 3,$ obtenemos $x_{2019} = 0,$ $x_{2020} = 1,$ $x_{2021} = 1,$ $x_{2022} = 0.$ La suma es $0 + 2 + 4 + 0 = 6.$

Por lo tanto, la respuesta correcta es A.

Since $S_n$ is the integer formed by the low $n$ bits, the condition $7S_n \equiv 1$ means $S_n \equiv 7^{-1} \pmod{2^n}$ for every $n.$ Thus the digits $x_k$ are the base- $2$ digits of $\tfrac17$ as a $2$ -adic number.

Long division in base $2$ gives digits $x_0 = x_1 = x_2 = 1,$ and thereafter the block repeats with period $3:$ for $k \ge 1,$ $x_k = 0$ exactly when $k$ is divisible by $3,$ and $x_k = 1$ otherwise.

Since $2019$ and $2022$ are both divisible by $3,$ while $2020 \equiv 1$ and $2021 \equiv 2 \pmod 3,$ we get $x_{2019} = 0,$ $x_{2020} = 1,$ $x_{2021} = 1,$ $x_{2022} = 0.$ The sum is $0 + 2 + 4 + 0 = 6.$

Thus, the correct answer is A.

2022 AMC 12B Problema 23

Respuesta: A

Nivel de dificultad: 2270

Pista pequeña:

Pista grande:

Solución:

El Problema 23 en otros años