2022 AMC 12B Problems/Problem 23

The following problem is from both the 2022 Fall AMC 12B #23 and 2022 Fall AMC 10B #25, so both problems redirect to this page.

Problem

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 \geqslant 1$ . What is the value of the sum $x_{2019} + 2x_{2020} + 4x_{2021} + 8x_{2022}$

$\textbf{(A)}~6\qquad\textbf{(B)}~7\qquad\textbf{(C)}~12\qquad\textbf{(D)}~14\qquad\textbf{(E)}~15\qquad$

Solution

First, notice that $x_{2019} + 2x_{2020} + 4x_{2021} + 8x_{2022} = \frac{S_{2023} - S_{2019}}{2^{2019}}$

Then since $S_n$ is the modular inverse of 7 in $\mathbb{Z}_{n}$ , we can perform the Euclidean algorithm to find it for $n = 2019,2023$ .

Starting with $2019$ , $7S_{2019} \equiv 1 \pmod{2^{2019}}$ $7S_{2019} = 2^{2019}k + 1$ Now, take both sides $\text{mod } 7$ $0 \equiv 2^{2019}k + 1 \pmod{7}$ Using Fermat's Little Theorem, $2^{2019} = (2^{288})^7 \cdot 2^3 \equiv 2^3 \equiv 1 \pmod{7}$ Thus, $0 \equiv k + 1 \pmod{7} \implies k \equiv 6 \pmod{7} \implies k = 7j + 6$ Therefore, $7S_{2019} = 2^{2019} (7j + 6) + 1 \implies S_{2019} = \frac{2^{2019} (7j + 6) + 1}{7}$

We may repeat this same calculation with $S_{2023}$ to yield $S_{2023} = \frac{2^{2023} (7h + 3) + 1}{7}$ Now, we notice that $S_n$ is basically an integer expressed in binary form with $n$ bits. This gives rise to a simple inequality, $0 \leqslant S_n \leqslant 2^n$ Since the maximum possible number that can be generated with $n$ bits is $\underbrace{{11111\dotsc1}_2}_{n} = \sum_{k=0}^{n-1} 2^k = 2^n - 1 \leqslant 2^n$ Looking at our calculations for $S_{2019}$ and $S_{2023}$ , we see that the only valid integers that satisfy that constraint are $j = h = 0$ $\frac{S_{2023} - S_{2019}}{2^{2019}} = \frac{\tfrac{2^{2023} \cdot 3 + 1}{7} - \tfrac{2^{2019} \cdot 6 + 1}{7}}{2^{2019}} = \frac{2^4 \cdot 3 - 6}{7} = \boxed{\textbf{(A)} \ 6}$ ~ $\color{magenta} zoomanTV$

2022 AMC 12B (Problems • Answer Key • Resources)
Preceded by Problem 22	Followed by Problem 24
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 12 Problems and Solutions

2022 AMC 10B (Problems • Answer Key • Resources)
Preceded by Problem 24	Followed by Last problem
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 10 Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.

Page

Toolbox

Search

2022 AMC 12B Problems/Problem 23

Problem

Solution

See Also