Competition · AMC preparation · step 4 of 4

AMC 10 · 2020A · #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 (x¹⁷+1)/(x+1), then drop further to the tiny prototype (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

Rewrite 289 as a power

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

(2²⁸⁹+1)/(2¹⁷+1) = (x¹⁷+1)/(x+1), x = 2¹⁷

2STEP 2

Use the odd-power factoring

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

(x¹⁷+1)/(x+1) = x¹⁶ - x¹⁵ + x¹⁴ - … + x² - x + 1

3STEP 3

Substitute back for x

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

Pair up the signed terms

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

Expand each pair in binary

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

List the exponent blocks

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

Count the bits

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.

Rewrite 289 as a power
Use the odd-power factoring
Substitute back for x
Pair up the signed terms
Expand each pair in binary
List the exponent blocks
Count the bits

A parent dashboard for the family lives at sensimlab.com.