AMC 10 · 2022 · #25

Grade 6 arithmetic

modular-arithmeticp-adic-inversepattern-recognitionrecursive-sequenceexponents easier-related-problempattern-recognitionsystematic-enumeration ↑ Prerequisites: modular-arithmeticrecursive-sequence

📏 Long solution 💡 4 insights

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 \geq 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$

Pick an answer.

(A)

(B)

(C)

(D)

(E)

View mode:

Toolkit + CCSS Solution

Understand

Restated: A sequence of bits $x_0, x_1, x_2, \dots \in \{0, 1\}$ is defined implicitly by the rule that $S_n := \sum_{k=0}^{n-1} x_k 2^k$ satisfies $7 S_n \equiv 1 \pmod{2^n}$ for every $n \ge 1$. (So $S_n$ is the $n$-bit binary number whose first $n$ bits agree with the unique 2-adic inverse of $7$.) Compute $x_{2019} + 2 x_{2020} + 4 x_{2021} + 8 x_{2022}$.

Givens: $x_k \in \{0, 1\}$ for every $k \ge 0$; $S_n = x_0 + 2 x_1 + 4 x_2 + \dots + 2^{n-1} x_{n-1}$; $7 S_n \equiv 1 \pmod{2^n}$ for every $n \ge 1$, which uniquely pins each $x_k$; Answer choices: (A) $6$, (B) $7$, (C) $12$, (D) $14$, (E) $15$

Unknowns: $x_{2019} + 2 x_{2020} + 4 x_{2021} + 8 x_{2022}$

Understand

Plan

Primary tool: #9 Solve an Easier Related Problem

Secondary: #5 Look for a Pattern, #2 Make a Systematic List, #13 Convert to Algebra, #3 Eliminate Possibilities

Tool #9 (Easier) — instead of attacking index $2019$ directly, first compute $S_3, S_6, S_9$ and read off bits $x_0, x_1, \dots, x_8$ by hand. Tool #5 (Pattern) — that small data set will reveal a period-$3$ pattern in the bits. Tool #2 (List) — list the first $9$ bits in groups of three to confirm the period. Tool #13 (Algebra) — once the pattern is known, plug $k = 2019, 2020, 2021, 2022$ into the pattern. Tool #3 (Eliminate) — check the answer against choices $\{6, 7, 12, 14, 15\}$.

Execute — Answer: A

#9 Solve an Easier Related Problem 6.NS.B.4 Step 1

Solve the easier problem: compute the first few $S_n$ by finding the multiplicative inverse of $7$ modulo $2^n$ for small $n$.
$n = 3$: $7 S_3 \equiv 1 \pmod{8}$.
Since $7 \equiv -1 \pmod 8$, $S_3 \equiv -1 \equiv 7 \pmod 8$.
With $0 \le S_3 < 8$, $S_3 = 7 = 111_2$, so $x_0 x_1 x_2 = 1, 1, 1$.

$$S_3 = 7 = 111_2 \;\Rightarrow\; x_0, x_1, x_2 = 1, 1, 1$$

💡 Grade 6 — find the inverse of $7$ modulo a small power of $2$ by inspection.

#9 Solve an Easier Related Problem 5.NBT.A.2 Step 2

$n = 6$: $7 S_6 \equiv 1 \pmod{64}$.
Try $S_6 = 55$: $7 \cdot 55 = 385 = 6 \cdot 64 + 1$ ✓.
$S_6 = 55 = 32 + 16 + 4 + 2 + 1 = 110111_2$ (read least-significant first: $1, 1, 1, 0, 1, 1$).
So $x_3, x_4, x_5 = 0, 1, 1$.

$$S_6 = 55 = 110111_2 \;\Rightarrow\; x_3, x_4, x_5 = 0, 1, 1$$

💡 Grade 5 — read off a binary expansion bit-by-bit.

#9 Solve an Easier Related Problem 5.NBT.A.2 Step 3

$n = 9$: $7 S_9 \equiv 1 \pmod{512}$.
Try $S_9 = 439$: $7 \cdot 439 = 3073 = 6 \cdot 512 + 1$ ✓.
$S_9 = 439 = 256 + 128 + 32 + 16 + 4 + 2 + 1 = 110110111_2$ (bits $1,1,1,0,1,1,0,1,1$).
So $x_6, x_7, x_8 = 0, 1, 1$.

$$S_9 = 439 = 110110111_2 \;\Rightarrow\; x_6, x_7, x_8 = 0, 1, 1$$

💡 Grade 5 — same bit-reading on a longer number.

#5 Look for a Pattern 4.OA.C.5 Step 4

Pattern.
The first nine bits are $(x_0,\dots,x_8) = (1,1,1, 0,1,1, 0,1,1)$.
Grouping in threes shows a period-$3$ pattern starting at index $3$: $(0,1,1)$ repeats forever.
So for $k \ge 3$: $x_k = 0$ if $k \equiv 0 \pmod 3$, $x_k = 1$ if $k \equiv 1 \pmod 3$, $x_k = 1$ if $k \equiv 2 \pmod 3$.

$$x_k = \begin{cases} 0 & k \equiv 0 \pmod 3 \\ 1 & k \equiv 1, 2 \pmod 3 \end{cases} \quad (k \ge 3)$$

💡 Grade 4 — three computed groups show a clear period-$3$ rule for the bit at each index.

#2 Make a Systematic List 4.OA.C.5 Step 5

Plug in $k = 2019, 2020, 2021, 2022$.
$2019 = 3 \cdot 673$, so $2019 \equiv 0 \pmod 3 \Rightarrow x_{2019} = 0$.
$2020 \equiv 1 \Rightarrow x_{2020} = 1$.
$2021 \equiv 2 \Rightarrow x_{2021} = 1$.
$2022 \equiv 0 \Rightarrow x_{2022} = 0$.

$$x_{2019} = 0, \; x_{2020} = 1, \; x_{2021} = 1, \; x_{2022} = 0$$

💡 Grade 4 — use the rule to look up each indexed bit.

#3 Eliminate Possibilities 4.OA.A.3 Step 6

Compute the target: $x_{2019} + 2 x_{2020} + 4 x_{2021} + 8 x_{2022} = 0 + 2 \cdot 1 + 4 \cdot 1 + 8 \cdot 0 = 2 + 4 = 6$.
Answer (A).

$$0 + 2 + 4 + 0 = 6 \;\Rightarrow\; \textbf{(A)}$$

💡 Grade 4 — multi-step whole-number arithmetic to finish.

[1] #9 6.NS.B.4 Solve the easier problem: compute the first few $S_n$ by finding the multiplicat

[2] #9 5.NBT.A.2 $n = 6$: $7 S_6 \equiv 1 \pmod{64}$. Try $S_6 = 55$: $7 \cdot 55 = 385 = 6 \cdot

[3] #9 5.NBT.A.2 $n = 9$: $7 S_9 \equiv 1 \pmod{512}$. Try $S_9 = 439$: $7 \cdot 439 = 3073 = 6 \

[4] #5 4.OA.C.5 Pattern. The first nine bits are $(x_0,\dots,x_8) = (1,1,1, 0,1,1, 0,1,1)$. Grou

[5] #2 4.OA.C.5 Plug in $k = 2019, 2020, 2021, 2022$. $2019 = 3 \cdot 673$, so $2019 \equiv 0 \p

[6] #3 4.OA.A.3 Compute the target: $x_{2019} + 2 x_{2020} + 4 x_{2021} + 8 x_{2022} = 0 + 2 \cd

Review

Reasonableness: Sanity. The pattern check is concrete: we computed three full triples of bits from three independent values of $n$, and they all match $(0, 1, 1)$ starting at $k=3$. The first triple $(1,1,1)$ is an edge case at the start. To double-check the periodicity, note that the rule $7 S_n \equiv 1 \pmod{2^n}$ encodes the 2-adic inverse of $7$, and since $7 = 2^3 - 1$, we have $\tfrac{1}{7} = -\tfrac{1}{1 - 2^3}$ which is a geometric series in $2^3$ — that's exactly why the bit pattern repeats with period $3$. The target value $6$ matches choice (A). Other choices $7, 12, 14, 15$ come from misreading one bit or shifting the period by $1$.

Alternative: Tool #13 (Algebra). Write $7 S_n = k_n \cdot 2^n + 1$ with $0 \le S_n < 2^n$, giving $k_n \in \{0, 1, \dots, 6\}$ uniquely from $k_n \cdot 2^n \equiv -1 \equiv 6 \pmod 7$. The powers of $2$ mod $7$ cycle $1, 2, 4, 1, 2, 4, \dots$ with period $3$. $2019 \equiv 0 \pmod 3$ gives $2^{2019} \equiv 1$, so $k_{2019} = 6$. $2023 \equiv 1 \pmod 3$ gives $2^{2023} \equiv 2$, so $k_{2023} \cdot 2 \equiv 6$, $k_{2023} = 3$. Then $S_{2023} - S_{2019} = \tfrac{3 \cdot 2^{2023} - 6 \cdot 2^{2019}}{7} = \tfrac{(48 - 6) \cdot 2^{2019}}{7} = 6 \cdot 2^{2019}$, so the target $= \tfrac{S_{2023} - S_{2019}}{2^{2019}} = 6$.

CCSS standards used (min grade 6)

4.OA.A.3 Solve multi-step word problems using the four operations with whole numbers (Final arithmetic $0 + 2 \cdot 1 + 4 \cdot 1 + 8 \cdot 0 = 6$.)
4.OA.C.5 Generate a number or shape pattern following a given rule (Recognizing and applying the period-$3$ pattern $x_k = 0, 1, 1$ (for $k \bmod 3 = 0, 1, 2$) to indices $2019, 2020, 2021, 2022$.)
5.NBT.A.2 Explain patterns in number of zeros and placement of decimal point when multiplying by powers of 10 (Reading binary expansions $7 = 111_2$, $55 = 110111_2$, $439 = 110110111_2$ to extract each bit.)
6.NS.B.4 Find greatest common factor and least common multiple of two whole numbers (Finding the multiplicative inverse of $7$ modulo $8, 64, 512$ ("what times $7$ leaves remainder $1$?").)

⭐ This AMC 10 problem only needs Grade 6 number-theory reasoning you already know — compute the bits $x_0, x_1, \dots, x_8$ by hand from three small cases $n = 3, 6, 9$, and a period-$3$ pattern $(0,1,1)$ jumps out for $k \ge 3$. Looking up $2019, 2020, 2021, 2022 \pmod 3$ gives bits $0, 1, 1, 0$, and the target $0 + 2 + 4 + 0 = 6$.