AMC 10 · 2020 · #21

Grade 8 arithmetic

Archetype Arithmetic Expression Decomposition

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

📏 Long solution 💡 3 insights

Problem

There exists a unique strictly increasing sequence of nonnegative integers $a_1 < a_2 < … < a_k$ such that $\frac{2^{289}+1}{2^{17}+1} = 2^{a_1} + 2^{a_2} + … + 2^{a_k}.$ What is $k?$

$\textbf{(A) } 117 \qquad \textbf{(B) } 136 \qquad \textbf{(C) } 137 \qquad \textbf{(D) } 273 \qquad \textbf{(E) } 306$

Pick an answer.

(A)

117

(B)

136

(C)

137

(D)

273

(E)

306

View mode:

Toolkit + CCSS Solution

Understand

Restated: Write the integer $\frac{2^{289}+1}{2^{17}+1}$ as a sum of distinct powers of $2$ with strictly increasing exponents $a_1 < a_2 < \cdots < a_k$. The question asks for $k$, the number of $1$s in the binary representation of this integer.

Givens: Numerator $2^{289}+1$, denominator $2^{17}+1$; $289 = 17 \times 17$, so the numerator and denominator share the structure $x^{17}+1$ and $x+1$ with $x = 2^{17}$; Output is a sum of distinct powers of $2$ with strictly increasing exponents; Answer choices: (A) $117$, (B) $136$, (C) $137$, (D) $273$, (E) $306$

Unknowns: $k$ = number of terms = number of $1$s in the binary representation

Understand

Plan

Primary tool: #9 Solve an Easier Related Problem

Secondary: #5 Look for a Pattern, #7 Identify Subproblems, #2 Make a Systematic List

Tool #9 (Easier Problem): the exponents $289$ and $17$ are huge — replace them with the substitution $x = 2^{17}$ to reveal a cleaner $\frac{x^{17}+1}{x+1}$, then drop further to the tiny prototype $\frac{x^3+1}{x+1}$ with $x=2^2$ to see the mechanism. Tool #5 (Pattern): the alternating polynomial quotient $x^{16} - x^{15} + \cdots + 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.

Execute — Answer: C

#9 Solve an Easier Related Problem 8.EE.A.1 Step 1

Notice $289 = 17 \times 17$.
Substitute $x = 2^{17}$.
Then $2^{289} = (2^{17})^{17} = x^{17}$, so the expression becomes $\frac{x^{17}+1}{x+1}$.
This is a clean polynomial division.

$$\dfrac{2^{289}+1}{2^{17}+1} = \dfrac{x^{17}+1}{x+1}, \quad x = 2^{17}$$

💡 Naming $x = 2^{17}$ turns a scary problem into the much friendlier $\frac{x^{17}+1}{x+1}$.

#5 Look for a Pattern 8.EE.A.1 Step 2

For odd $n$, the identity $x^n+1 = (x+1)(x^{n-1} - x^{n-2} + \cdots - x + 1)$ holds.
Check the easier case $n=3$: $(x+1)(x^2-x+1) = x^3+1$.
The same template with $n=17$ gives an alternating sum with $17$ terms.

$$\dfrac{x^{17}+1}{x+1} = x^{16} - x^{15} + x^{14} - \cdots + x^2 - x + 1$$

💡 The same alternating pattern that factors $x^3+1$ factors $x^{17}+1$ — just longer.

#9 Solve an Easier Related Problem 8.EE.A.1 Step 3

Put $x = 2^{17}$ back.
Each $x^j = 2^{17j}$, so the quotient is an alternating sum of $17$ powers of $2$: $2^{272}, 2^{255}, 2^{238}, \ldots, 2^{34}, 2^{17}, 1$, with signs $+, -, +, -, \ldots, +, -, +$.

$$2^{272} - 2^{255} + 2^{238} - 2^{221} + \cdots + 2^{34} - 2^{17} + 2^0$$

💡 Each polynomial term becomes one power of $2$; signs alternate, ending with $+1$.

#7 Identify Subproblems 8.EE.A.1 Step 4

There are $17$ signed terms: $9$ positives at exponents $272, 238, 204, \ldots, 34, 0$ and $8$ negatives at $255, 221, \ldots, 17$.
Pair the leading positive with the next negative: $(2^{272} - 2^{255}) + (2^{238} - 2^{221}) + \cdots + (2^{34} - 2^{17})$, plus the lone $+1$ at the end.
That is $8$ pairs $+$ one extra.

$$\underbrace{(2^{272}-2^{255})}_{\text{pair 1}} + \underbrace{(2^{238}-2^{221})}_{\text{pair 2}} + \cdots + \underbrace{(2^{34}-2^{17})}_{\text{pair 8}} + 1$$

💡 Group $+,-$ adjacent terms into $8$ pairs; the rightmost $+1$ has no partner.

#9 Solve an Easier Related Problem 8.EE.A.1 Step 5

Each pair is $2^A - 2^B$ with $A - B = 17$.
Factor the smaller out: $2^A - 2^B = 2^B(2^{17} - 1)$.
The key easier fact: $2^{17} - 1 = 2^{16} + 2^{15} + \cdots + 2^1 + 2^0$, i.e.
$17$ consecutive $1$-bits (just like $2^3 - 1 = 4 + 2 + 1$).
So each pair expands to exactly $17$ distinct powers of $2$.

$$2^A - 2^B = 2^B(2^{17}-1) = 2^{A-1} + 2^{A-2} + \cdots + 2^{B+1} + 2^B$$

💡 $2^{17} - 1$ in binary is seventeen $1$s in a row — a tiny pattern reused $8$ times.

#2 Make a Systematic List 8.EE.A.1 Step 6

List the exponent blocks.
Pair $i$ (for $i = 1, \ldots, 8$) covers exponents $[B_i, B_i+16]$ where $B_8 = 17, B_7 = 51, \ldots, B_1 = 255$.
Concretely: pair 8 fills $[17, 33]$, pair 7 fills $[51, 67]$, pair 6 fills $[85, 101]$, $\ldots$, pair 1 fills $[255, 271]$.
Each block has $17$ exponents and the blocks are disjoint (gap of $17$ between consecutive blocks).

$$\text{blocks: } [17,33], [51,67], [85,101], \ldots, [255,271]; \;\; 8 \text{ blocks of width } 17$$

💡 Each pair fills a clean $17$-wide window of exponents — no overlaps.

#2 Make a Systematic List 8.EE.A.1 Step 7

Count the bits.
The $8$ blocks contribute $8 \times 17 = 136$ distinct exponents.
The leftover $+1 = 2^0$ uses exponent $0$, which is below the smallest block's start $17$, so it is a new bit.
Total: $136 + 1 = 137$.

$$k = 8 \times 17 + 1 = 136 + 1 = 137 \Rightarrow \textbf{(C)}$$

💡 Eight $17$-bit blocks plus one stand-alone bit $= 137$.

[1] #9 8.EE.A.1 Notice $289 = 17 \times 17$. Substitute $x = 2^{17}$. Then $2^{289} = (2^{17})^{

[2] #5 8.EE.A.1 For odd $n$, the identity $x^n+1 = (x+1)(x^{n-1} - x^{n-2} + \cdots - x + 1)$ ho

[3] #9 8.EE.A.1 Put $x = 2^{17}$ back. Each $x^j = 2^{17j}$, so the quotient is an alternating s

[4] #7 8.EE.A.1 There are $17$ signed terms: $9$ positives at exponents $272, 238, 204, \ldots,

[5] #9 8.EE.A.1 Each pair is $2^A - 2^B$ with $A - B = 17$. Factor the smaller out: $2^A - 2^B =

[6] #2 8.EE.A.1 List the exponent blocks. Pair $i$ (for $i = 1, \ldots, 8$) covers exponents $[B

[7] #2 8.EE.A.1 Count the bits. The $8$ blocks contribute $8 \times 17 = 136$ distinct exponents

Review

Reasonableness: Magnitude check: the quotient is about $\frac{2^{289}}{2^{17}} = 2^{272}$, which has $\le 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^0$; (C) $137$ is correct. Spot-check with the tiny case $\frac{2^9+1}{2^3+1} = \frac{513}{9} = 57 = 32 + 16 + 8 + 1 = 2^5 + 2^4 + 2^3 + 2^0$, which has $k=4$ bits. Using the same formula: $9 = 3 \cdot 3$, alternating polynomial has $3$ terms ($1$ pair $+$ trailing $1$), so $k = 1 \cdot 3 + 1 = 4$. Matches.

Alternative: Tool #5 (Pattern) without algebra: try the smaller analogues $\frac{2^9+1}{2^3+1}$ ($n=3, x = 2^3$, $k = 4$) and $\frac{2^{25}+1}{2^5+1}$ ($n=5, x = 2^5$, $k = 1 \cdot 5 + 1 = 6$... or $2 \cdot 5 + 1 = 11$? Re-derive: pairs $= (n-1)/2 = 2$, contributes $2 \cdot 5 = 10$, plus $1$ gives $k=11$). For general $\frac{2^{n^2}+1}{2^n+1}$ with odd $n$, the formula is $k = \frac{n-1}{2} \cdot n + 1$. Plug $n = 17$: $k = 8 \cdot 17 + 1 = 137$. Same answer via pure pattern induction.

CCSS standards used (min grade 8)

8.EE.A.1 Know and apply the properties of integer exponents (Rewriting $2^{289} = (2^{17})^{17}$, factoring $2^A - 2^B = 2^B(2^{A-B}-1)$, and expanding $2^{17}-1$ as a sum of distinct powers of $2$.)

⭐ This AMC 10 problem only needs Grade 8 exponent rules you already know: rename $x = 2^{17}$ to shrink the fraction to $\frac{x^{17}+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 \times 17 + 1 = 137$.

Problem

Toolkit + CCSS Solution

Understand

Plan

Execute — Answer: C

Review

CCSS standards used (min grade 8)

More like this