Question

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}?$

$6$

$7$

$12$

$14$

$15$

Answer: A

Concepts:modular arithmetic number base power of 2

Difficulty rating: 2390

Small Hint:

Find $S_{2019}$ and $S_{2023},$ then subtract to isolate the four digits

Big Hint:

The congruence defines the binary digits of the inverse of $7$

Solution:

The desired sum is $\frac{S_{2023}-S_{2019}}{2^{2019}}.$ Also, $0\le S_n<2^n.$

Therefore, for a unique $m_n\in\{0,1,\ldots,6\},$ $7S_n=m_n2^n+1.$ Reducing modulo $7$ gives $m_n2^n\equiv-1\pmod7.$

Since $2^3\equiv1\pmod7$ and $2019\equiv0\pmod3,$ we get $m_{2019}=6.$ Since $2023\equiv1\pmod3,$ we have $2m_{2023}\equiv-1\pmod7,$ so $m_{2023}=3.$ Hence $\begin{gathered}S_{2019}=\frac{6\cdot2^{2019}+1}{7},\\ S_{2023}=\frac{3\cdot2^{2023}+1}{7}.\end{gathered}$

Finally, $\frac{S_{2023}-S_{2019}}{2^{2019}} =\frac{3\cdot2^4-6}{7}=6.$

Thus, the correct answer is A .

2022 AMC 10B Problem 25

Answer: A

Difficulty rating: 2390

Small Hint:

Big Hint:

Solution:

Problem 25 in Other Years