2020 AMC 10A Problems/Problem 21

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$

Solution 1

First, substitute $2^{17}$ with $a$ . Then, the given equation becomes $\frac{a^{17}+1}{a+1}=a^{16}-a^{15}+a^{14}...-a^1+a^0$ . Now consider only $a^{16}-a^{15}$ . This equals $a^{15}(a-1)=a^{15}*(2^{17}-1)$ . Note that $2^{17}-1$ equals $2^{16}+2^{15}+...+1$ , since the sum of a geometric sequence is $\frac{a^n-1}{a-1}$ . Thus, we can see that $a^{16}-a^{15}$ forms the sum of 17 different powers of 2. Applying the same method to each of $a^{14}-a^{13}$ , $a^{12}-a^{11}$ , ... , $a^{2}-a^{1}$ , we can see that each of the pairs forms the sum of 17 different powers of 2. This gives us $17*8=136$ . But we must count also the $a^0$ term. Thus, Our answer is $136+1=\boxed{\textbf{(C) } 137}$ .

~seanyoon777

Solution 2

(This is similar to solution 1) Let $x = 2^{17}$ . Then, $2^{289} = x^{17}$ . The LHS can be rewritten as $\frac{x^{17}+1}{x+1}=x^{16}-x^{15}+\cdots+x^2-x+1=(x-1)(x^{15}+x^{13}+\cdots+x^{1})+1$ . Plugging $2^{17}$ back in for $x$ , we have $(2^{17}-1)(2^{15+17}+2^{13+17}+\cdots+2^{1+17})+1=(2^{16}+2^{15}+\cdots+2^{1})(2^{15\cdot17}+2^{13\cdot17}+\cdots+2^{1\cdot17})+1$ . When expanded, this will have $17\cdot8+1=137$ terms. Therefore, our answer is $\boxed{\textbf{(C) } 137}$ .

Solution 3

Note that the expression is equal to something slightly lower than $2^{272}$ . Clearly, answer choices $(D)$ and $(E)$ make no sense because the lowest sum for $273$ terms is $2^{273}-1$ . Now, $(A)$ makes no sense. $(B)$ and $(C)$ are 1 apart, but because the expression is odd, it will have to contain $2^0=1$ , and because $(C)$ is $1$ bigger, the answer is $\boxed{\textbf{(C) } 137}$ .

~Lcz

Video Solution

https://youtu.be/Ozp3k2464u4

~IceMatrix

2020 AMC 10A (Problems • Answer Key • Resources)
Preceded by Problem 20	Followed by Problem 22
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25
All AMC 10 Problems and Solutions

Page

Toolbox

Search

2020 AMC 10A Problems/Problem 21

Contents

Solution 1

Solution 2

Solution 3

Video Solution

See Also