AMC10 2022 B

AMC10 2022 B · Q25

AMC10 2022 B · Q25. It mainly tests Remainders & modular arithmetic, Sequences in number theory (remainders patterns).

Let $x_0,x_1,x_2,\dotsc$ 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 $7S_n \equiv 1 \pmod{2^n}$ for all $n \geq 1$. What is the value of the sum \[x_{2019} + 2x_{2020} + 4x_{2021} + 8x_{2022}?\]

设 $x_0,x_1,x_2,\dotsc$ 是一个数列，其中每个 $x_k$ 要么是 $0$ 要么是 $1$。对于每个正整数 $n$，定义 \[S_n = \sum_{k=0}^{n-1} x_k 2^k\] 假设对所有 $n \geq 1$ 有 $7S_n \equiv 1 \pmod{2^n}$。求和 \[x_{2019} + 2x_{2020} + 4x_{2021} + 8x_{2022}\] 的值。

(A) 6 6

(B) 7 7

(D) 14 14

(E) 15 15

Answer

Correct choice: (A)

正确答案：（A）

Solution

In binary numbers, we have \[S_n = (x_{n-1} x_{n-2} x_{n-3} x_{n-4} \ldots x_{2} x_{1} x_{0})_2.\] It follows that \[8S_n = (x_{n-1} x_{n-2} x_{n-3} x_{n-4} \ldots x_{2} x_{1} x_{0}000)_2.\] We obtain $7S_n$ by subtracting the equations: \[\begin{array}{clccrccccccr} & (x_{n-1} & x_{n-2} & x_{n-3} & x_{n-4} & \ldots & x_2 & x_1 & x_0 & 0 & 0 & 0 \ )_2 \\ -\quad & & & & (x_{n-1} & \ldots & x_5 & x_4 & x_3 & x_2 & x_1 & x_0)_2 \\ \hline & & & & & & & & & & & \\ [-2.5ex] & ( \ \ ?& ? & ? & 0 \ \ \ & \ldots & 0 & 0 & 0 & 0 & 0 & 1 \ )_2 \\ \end{array}\] We work from right to left: \begin{alignat*}{6} x_0=x_1=x_2=1 \quad &\implies \quad &x_3 &= 0& \\ \quad &\implies \quad &x_4 &= 1& \\ \quad &\implies \quad &x_5 &= 1& \\ \quad &\implies \quad &x_6 &= 0& \\ \quad &\implies \quad &x_7 &= 1& \\ \quad &\implies \quad &x_8 &= 1& \\ \quad &\quad \vdots & & & \end{alignat*} For all $n\geq3,$ we conclude that - $x_n=0$ if and only if $n\equiv 0\pmod{3}.$ - $x_n=1$ if and only if $n\not\equiv 0\pmod{3}.$ Finally, we get $(x_{2019},x_{2020},x_{2021},x_{2022})=(0,1,1,0),$ from which \[x_{2019} + 2x_{2020} + 4x_{2021} + 8x_{2022} = \boxed{\textbf{(A) } 6}.\]

在二进制数中，我们有 \[S_n = (x_{n-1} x_{n-2} x_{n-3} x_{n-4} \ldots x_{2} x_{1} x_{0})_2.\] 由此 \[8S_n = (x_{n-1} x_{n-2} x_{n-3} x_{n-4} \ldots x_{2} x_{1} x_{0}000)_2.\] 通过减法得到 $7S_n$： \[\begin{array}{clccrccccccr} & (x_{n-1} & x_{n-2} & x_{n-3} & x_{n-4} & \ldots & x_2 & x_1 & x_0 & 0 & 0 & 0 \ )_2 \\ -\quad & & & & (x_{n-1} & \ldots & x_5 & x_4 & x_3 & x_2 & x_1 & x_0)_2 \\ \hline & & & & & & & & & & & \\ [-2.5ex] & ( \ \ ?& ? & ? & 0 \ \ \ & \ldots & 0 & 0 & 0 & 0 & 0 & 1 \ )_2 \\ \end{array}\] 我们从右向左计算： \begin{alignat*}{6} x_0=x_1=x_2=1 \quad &\implies \quad &x_3 &= 0& \\ \quad &\implies \quad &x_4 &= 1& \\ \quad &\implies \quad &x_5 &= 1& \\ \quad &\implies \quad &x_6 &= 0& \\ \quad &\implies \quad &x_7 &= 1& \\ \quad &\implies \quad &x_8 &= 1& \\ \quad &\quad \vdots & & & \end{alignat*} 对于所有 $n\geq3$，我们得出 - $x_n=0$ 当且仅当 $n\equiv 0\pmod{3}$。 - $x_n=1$ 当且仅当 $n\not\equiv 0\pmod{3}$。最后，我们得到 $(x_{2019},x_{2020},x_{2021},x_{2022})=(0,1,1,0)$，由此 \[x_{2019} + 2x_{2020} + 4x_{2021} + 8x_{2022} = \boxed{\textbf{(A) } 6}.\]

Topics