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
A sequence of bits x₀, x₁, x₂, … ∈ {0, 1} is defined implicitly by the rule that S_n := Σ_k=0ⁿ⁻¹ x_k 2^k satisfies 7 S_n ≡ 1 (mod 2ⁿ) for every n ≥ 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₂019 + 2 x₂020 + 4 x₂021 + 8 x₂022.

Pick an answer.

(A)
6
(B)
7
(C)
12
(D)
14
(E)
15

AMC 10 2022 problem © Mathematical Association of America (MAA AMC). Reproduced for educational use.

How to solve
Strategy Solve an Easier Related Problem

Tool #9 (Easier) — instead of attacking index 2019 directly, first compute S₃, S₆, S₉ and read off bits x₀, x₁, …, x₈ 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}.

1STEP 1

For n = 3, 7 ≡ -1 (mod 8) gives S₃ = 7 = 111₂, so x₀, x₁, x₂ = 1, 1, 1.

S₃ = 7 = 111₂ → x₀, x₁, x₂ = 1, 1, 1
2STEP 2

For n = 6, S₆ = 55 = 110111₂ read low bits first gives x₃, x₄, x₅ = 0, 1, 1.

S₆ = 55 = 110111₂ → x₃, x₄, x₅ = 0, 1, 1
3STEP 3

For n = 9, S₉ = 439 = 110110111₂; reading the low bits gives x₆, x₇, x₈ = 0, 1, 1.

S₉ = 439 = 110110111₂ → x₆, x₇, x₈ = 0, 1, 1
4STEP 4

Grouping the first nine bits in threes reveals a period-3 pattern (0, 1, 1) for every k ≥ 3.

x_k = 0 & k ≡ 0 (mod 3) ; 1 & k ≡ 1, 2 (mod 3) (k ≥ 3)
5STEP 5

Since 2019 ≡ 0, 2020 ≡ 1, 2021 ≡ 2, 2022 ≡ 0 mod 3, the rule gives x₂019 = 0, x₂020 = 1, x₂021 = 1, x₂022 = 0.

x₂019 = 0, x₂020 = 1, x₂021 = 1, x₂022 = 0
6STEP 6

Combine with weights 1, 2, 4, 8: 0 + 2 + 4 + 0 = 6, choice (A).

0 + 2 + 4 + 0 = 6 → (A)
Answer
6
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 ≡ 1 (mod 2ⁿ) encodes the 2-adic inverse of 7, and since 7 = 2³ - 1, we have 17\frac{1}{7} = −11−23-\frac{1}{1 - 2³} which is a geometric series in 2³ — 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.
💡Key takeaway

This AMC 10 problem only needs Grade 6 number-theory reasoning you already know — compute the bits x₀, x₁, …, x₈ by hand from three small cases n = 3, 6, 9, and a period-3 pattern (0,1,1) jumps out for k ≥ 3. Looking up 2019, 2020, 2021, 2022 mod 3 gives bits 0, 1, 1, 0, and the target 0 + 2 + 4 + 0 = 6.