Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2020 AMC 10A Problems/Problem 21"

(→‎Solution 3)
(New solution)
Line 24: Line 24:
  
 
~Lcz
 
~Lcz
 +
 +
== Solution 4 ==
 +
In order to shorten expressions, <math>\#</math> will represent <math>16</math> consecutive <math>0</math>s when expressing numbers. <br>
 +
<br>
 +
Think of the problem in binary. We have <br>
 +
<math>\frac{1\#0\#0\#0\#0\#0\#0\#0\#0\#0\#0\#0\#0\#0\#0\#0\#0\#1_2}{1\#1_2}</math> <br>
 +
Note that <br>
 +
<math>(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)</math> <br>
 +
<math>= 1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1_2</math> <br>
 +
and <br>
 +
<math>(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)</math> <br>
 +
<math>= 1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#0_2</math> <br>
 +
<br>
 +
Since <br>
 +
<math>\phantom{=\ } 1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1_2</math> <br>
 +
<math>-\ \phantom{1\#} 1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#1\#0_2</math> <br>
 +
<math>= 1\#0\#0\#0\#0\#0\#0\#0\#0\#0\#0\#0\#0\#0\#0\#0\#0\#1_2</math> <br>
 +
this means that<br>
 +
<math>(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}</math> <br>
 +
so <br>
 +
<math>\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})</math> <br>
 +
<math>= 2^0 + (2^{34} - 2^{17}) + (2^{68} - 2^{51}) + \cdots + (2^{272} - 2^{255})</math> <br>
 +
<br>
 +
Expressing each of the pairs of the form <math>2^{n + 17} - 2^n</math> in binary, we have <br>
 +
<math>\phantom{=\ } 1000000000000000000 \cdots 0_2</math> <br>
 +
<math>-\ \phantom{10000000000000000} 10 \cdots 0_2</math> <br>
 +
<math>= \phantom{1} 111111111111111110 \cdots 0_2</math> <br>
 +
or <br>
 +
<math>2^{n + 17} - 2^n = 2^{n + 16} + 2^{n + 15} + 2^{n + 14} + \cdots + 2^{n}</math> <br>
 +
This means that each pair has <math>17</math> terms of the form <math>2^n</math>. <br>
 +
<br>
 +
Since there are <math>8</math> of these pairs, there are a total of <math>8 \cdot 17 = 136</math> terms. Accounting for the <math>2^0</math> term, which was not in the pair, we have a total of <math>136 + 1 = \boxed{\textbf{(C) } 137}</math> terms.
  
 
==Video Solution==
 
==Video Solution==

Revision as of 23:30, 1 February 2020

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\cdot{17}}+2^{13\cdot{17}}+\cdots+2^{1\cdot{17}})+1=(2^{16}+2^{15}+\cdots+2^{0})(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$. $(A)$ just 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

Solution 4

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.

Video Solution

https://youtu.be/Ozp3k2464u4

~IceMatrix

See Also

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
2020 AMC 12A (Problems • Answer Key • Resources)
Preceded by
Problem 18 		Followed by
Problem 20
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 12 Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2020_AMC_10A_Problems/Problem_21&oldid=116550"