AMC 10 · 2020 · #21

Grade 8 arithmetic

Archetype Arithmetic Expression Decomposition └ Sub-archetype Multi-Segment Path or Count Sum

polynomial-factoringbase-conversionexponentssequences-geometricpattern-recognition identify-subproblemspattern-recognitioneasier-related-problem ↑ Prerequisites: polynomial-factoringbase-conversion

📏 Long solution 💡 3 insights

Problem

Write the integer

\frac{2²⁸⁹+1}{2¹⁷+1}

as a sum of distinct powers of 2 with strictly increasing exponents a₁ ＜ a₂ ＜ … ＜ a_k. The question asks for k, the number of 1s in the binary representation of this integer.

Pick an answer.

(A)

117

(B)

136

(C)

137

(D)

273

(E)

306

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

How to solve

Strategy Solve an Easier Related Problem

Tool #9 (Easier Problem): the exponents 289 and 17 are huge — replace them with the substitution x = 2¹⁷ to reveal a cleaner $\frac{x¹⁷+1}{x+1}$ , then drop further to the tiny prototype $\frac{x³+1}{x+1}$ with x=2² to see the mechanism. Tool #5 (Pattern): the alternating polynomial quotient x¹⁶ - x¹⁵ + … + 1 is a clean pattern. Tool #7 (Subproblems): split each subtraction 2^A - 2^B into a string of 1-bits. Tool #2 (Systematic List): once we know each pair contributes 17 bits, list the pair-blocks and sum.

1STEP 1

Notice 289 = 17 × 17 and set x = 2¹⁷, turning the fraction into the clean $\frac{x¹⁷+1}{x+1}$ .

\frac{2²⁸⁹+1}{2¹⁷+1}

\frac{x¹⁷+1}{x+1}

, x = 2¹⁷

2STEP 2

For odd n, xⁿ+1 = (x+1)(xⁿ⁻¹−…+1), so the quotient is x¹⁶ − x¹⁵ + … − x + 1 — 17 alternating terms.

\frac{x¹⁷+1}{x+1}

= x¹⁶ - x¹⁵ + x¹⁴ - … + x² - x + 1

3STEP 3

Put x = 2¹⁷ back (xʲ = 2¹⁷ʲ), so the quotient is 2²⁷² − 2²⁵⁵ + 2²³⁸ − … + 2³⁴ − 2¹⁷ + 1.

2²⁷² - 2²⁵⁵ + 2²³⁸ - 2²²¹ + … + 2³⁴ - 2¹⁷ + 2⁰

4STEP 4

Group the 17 signed terms into 8 pairs (2^A − 2^B) plus a lone +1: (2²⁷²−2²⁵⁵) + … + (2³⁴−2¹⁷) + 1.

(2²⁷²-2²⁵⁵)_pair 1 + (2²³⁸-2²²¹)_pair 2 + … + (2³⁴-2¹⁷)_pair 8 + 1

5STEP 5

Each pair 2^A − 2^B = 2^B(2¹⁷−1), and 2¹⁷−1 is 17 consecutive 1-bits, so every pair expands to 17 distinct powers of 2.

2^A - 2^B = 2^B(2¹⁷-1) = 2^A-1 + 2^A-2 + … + 2^B+1 + 2^B

6STEP 6

Each pair fills a 17-wide exponent block — [17,33], [51,67], …, [255,271] — 8 disjoint blocks with gaps of 17.

blocks: [17,33], [51,67], [85,101], …, [255,271]; 8 blocks of width 17

7STEP 7

The 8 blocks give 8 × 17 = 136 bits; the lone 2⁰ adds one more, so k = 137 → (C).

k = 8 × 17 + 1 = 136 + 1 = 137 → (C)

Answer

137

Magnitude check: the quotient is about

\frac{2²⁸⁹}{2¹⁷}

= 2²⁷², which has ≤ 273 bits total. Among the 273 possible bit positions, k = 137 are 1 — roughly half, which matches the alternating-then-fill pattern. Choice (D) 273 is the bit-length, a trap; (B) 136 misses the lone 2⁰; (C) 137 is correct. Spot-check with the tiny case

\frac{2⁹+1}{2³+1}

\frac{513}{9}

= 57 = 32 + 16 + 8 + 1 = 2⁵ + 2⁴ + 2³ + 2⁰, which has k=4 bits. Using the same formula: 9 = 3 · 3, alternating polynomial has 3 terms (1 pair + trailing 1), so k = 1 · 3 + 1 = 4. Matches.

💡Key takeaway

This AMC 10 problem only needs Grade 8 exponent rules you already know: rename x = 2¹⁷ to shrink the fraction to $\frac{x¹⁷+1}{x+1}$ , expand into 17 alternating powers of 2, pair them up so each pair becomes 17 consecutive 1-bits in binary, and add: 8 × 17 + 1 = 137.

More like this