AMC 10 · 2022 · #23

Grade 6 arithmetic

Archetype Modular Cycle Frequency Count └ Sub-archetype Position-in-Cycle Lookup

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

📏 Long solution 💡 4 insights

Problem

A sequence of bits is defined implicitly: the number built from its first n bits, multiplied by seven, always leaves remainder one modulo two to the n. Compute the weighted sum of the bits in positions 2019 through 2022 with weights one, two, four, and eight.

Pick an answer.

(A)

(B)

(C)

(D)

(E)

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

Find the first three bits

Compute the first three directly.

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

2STEP 2

Find the next three

Compute the next three too.

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

3STEP 3

And the three after

Compute the third batch.

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

4STEP 4

Spot the repeating pattern

The bits repeat every three.

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

5STEP 5

Read the four bits

Read the four bits from the remainders.

x₂₀₁₉ = 0, x₂₀₂₀ = 1, x₂₀₂₁ = 1, x₂₀₂₂ = 0

6STEP 6

Take the weighted sum

The weighted sum is 6.

0 + 2 + 4 + 0 = 6 → (A)

Answer

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 1/7 = -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 12 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.