# 2020 AMC 10A Problems/Problem 21

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
The following problem is from both the 2020 AMC 12A #19 and 2020 AMC 10A #21, so both problems redirect to this page.

## 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$

## Solution 1

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

~seanyoon777

## Solution 2 (Intuitive)

Multiply both sides by $2^{17}+1$ to get $$2^{289}+1=2^{a_1} + 2^{a_2} + … + 2^{a_k} + 2^{a_1+17} + 2^{a_2+17} + … + 2^{a_k+17}.$$

Notice that $a_1 = 0$, since there is a $1$ on the LHS. However, now we have an extra term of $2^{18}$ on the right from $2^{a_1+17}$. To cancel it, we let $a_2 = 18$. The two $2^{18}$'s now combine into a term of $2^{19}$, so we let $a_3 = 19$. And so on, until we get to $a_{18} = 34$. Now everything we don't want telescopes into $2^{35}$. We already have that term since we let $a_2 = 18 \implies a_2+17 = 35$. Everything from now on will automatically telescope to $2^{52}$. So we let $a_{19}$ be $52$.

As you can see, we will have to add $17$ $a_n$'s at a time, then "wait" for the sum to automatically telescope for the next $17$ numbers, etc, until we get to $2^{289}$. We only need to add $a_n$'s between odd multiples of $17$ and even multiples. The largest even multiple of $17$ below $289$ is $17\cdot16$, so we will have to add a total of $17\cdot 8$ $a_n$'s. However, we must not forget we let $a_1=0$ at the beginning, so our answer is $17\cdot8+1 = \boxed{\textbf{(C) } 137}$.

## Solution 3

In order to shorten expressions, $\#$ will represent $16$ consecutive $0$s when expressing numbers.

Think of the problem in binary. We have
$\frac{1\#0\#0\#0\#0\#0\#0\#0\#0\#0\#0\#0\#0\#0\#0\#0\#0\#1_2}{1\#1_2}$
Note that
$(2^{17} + 1) (2^0 + 2^{34} + 2^{68} + \cdots + 2^{272}) = 2^0(2^{17} + 1) + 2^{34}(2^{17} + 1) + 2^{68}(2^{17} + 1) + \cdots 2^{272}(2^{17} + 1)$
$= 1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1_2$
and
$(2^{17} + 1) (2^{17} + 2^{51} + 2^{85} + \cdots + 2^{255}) = 2^{17}(2^{17} + 1) + 2^{51}(2^{17} + 1) + 2^{85}(2^{17} + 1) + \cdots 2^{255}(2^{17} + 1)$
$= 1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#0_2$

Since
$\phantom{=\ } 1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1_2$
$-\ \phantom{1\#} 1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#0_2$
$= 1\#0\#0\#0\#0\#0\#0\#0\#0\#0\#0\#0\#0\#0\#0\#0\#0\#1_2$
this means that
$(2^{17} + 1) (2^0 + 2^{34} + 2^{68} + \cdots + 2^{272}) - (2^{17} + 1) (2^{17} + 2^{51} + 2^{85} + \cdots + 2^{255}) = 2^{289}$
so
$\frac{2^{289}+1}{2^{17}+1} = (2^0 + 2^{34} + 2^{68} + \cdots + 2^{272}) - (2^{17} + 2^{51} + 2^{85} + \cdots + 2^{255})$
$= 2^0 + (2^{34} - 2^{17}) + (2^{68} - 2^{51}) + \cdots + (2^{272} - 2^{255})$

Expressing each of the pairs of the form $2^{n + 17} - 2^n$ in binary, we have
$\phantom{=\ } 1000000000000000000 \cdots 0_2$
$-\ \phantom{10000000000000000} 10 \cdots 0_2$
$= \phantom{1} 111111111111111110 \cdots 0_2$
or
$2^{n + 17} - 2^n = 2^{n + 16} + 2^{n + 15} + 2^{n + 14} + \cdots + 2^{n}$
This means that each pair has $17$ terms of the form $2^n$.

Since there are $8$ of these pairs, there are a total of $8 \cdot 17 = 136$ terms. Accounting for the $2^0$ term, which was not in the pair, we have a total of $136 + 1 = \boxed{\textbf{(C) } 137}$ terms. ~emerald_block

## Solution 4(Fake: only use if you have no time and quite freaking stupid)

Notice that the only answer choices that are spaced one apart are $136$ and $137$. It's likely that people will forget to include the final term so the answer is $\boxed{137}$.

## Video Solutions

### Video Solution 1 (Simple)

~Education The Study of Everything

~IceMatrix

~savannahsolver