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 2)
 
(56 intermediate revisions by 29 users not shown)
Line 1: Line 1:
 +
{{duplicate|[[2020 AMC 12A Problems|2020 AMC 12A #19]] and [[2020 AMC 10A Problems|2020 AMC 10A #21]]}}
 +
 +
== Problem ==
 
There exists a unique strictly increasing sequence of nonnegative integers <math>a_1 < a_2 < … < a_k</math> such that<cmath>\frac{2^{289}+1}{2^{17}+1} = 2^{a_1} + 2^{a_2} + … + 2^{a_k}.</cmath>What is <math>k?</math>
 
There exists a unique strictly increasing sequence of nonnegative integers <math>a_1 < a_2 < … < a_k</math> such that<cmath>\frac{2^{289}+1}{2^{17}+1} = 2^{a_1} + 2^{a_2} + … + 2^{a_k}.</cmath>What is <math>k?</math>
  
Line 4: Line 7:
  
 
== Solution 1 ==
 
== Solution 1 ==
−
First, substitute <math>2^{17}</math> with <math>a</math>.  
+
First, substitute <math>2^{17}</math> with <math>x</math>.  
−
Then, the given equation becomes <math>\frac{a^{17}+1}{a+1}=a^{16}-a^{15}+a^{14}...-a^1+a^0</math>.
+
Then, the given equation becomes <math>\frac{x^{17}+1}{x+1}=x^{16}-x^{15}+x^{14}...-x^1+x^0</math> by sum of powers factorization.
−
Now consider only <math>a^{16}-a^{15}</math>. This equals <math>a^{15}(a-1)=a^{15}*(2^{17}-1)</math>.
+
Now consider only <math>x^{16}-x^{15}</math>. This equals <math>x^{15}(x-1)=x^{15} \cdot (2^{17}-1)</math>.
−
Note that <math>2^{17}-1</math> equals <math>2^{16}+2^{15}+...+1</math>, since the sum of a geometric sequence is <math>\frac{a^n-1}{a-1}</math>.
+
Note that <math>2^{17}-1</math> equals <math>2^{16}+2^{15}+...+1</math>, by difference of powers factorization (or by considering the expansion of <math>2^{17}=2^{16}+2^{15}+...+2+2</math>).
−
Thus, we can see that <math>a^{16}-a^{15}</math> forms the sum of 17 different powers of 2.  
+
Thus, we can see that <math>x^{16}-x^{15}</math> forms the sum of 17 different powers of 2.  
−
Applying the same method to each of <math>a^{14}-a^{13}</math>, <math>a^{12}-a^{11}</math>, ... , <math>a^{2}-a^{1}</math>, we can see that each of the pairs forms the sum of 17 different powers of 2. This gives us <math>17*8=136</math>.
+
Applying the same method to each of <math>x^{14}-x^{13}</math>, <math>x^{12}-x^{11}</math>, ... , <math>x^{2}-x^{1}</math>, we can see that each of the pairs forms the sum of 17 different powers of 2. This gives us <math>17 \cdot 8=136</math>.
−
But we must count also the <math>a^0</math> term.  
+
But we must count also the <math>x^0</math> term.  
 
Thus, Our answer is <math>136+1=\boxed{\textbf{(C) } 137}</math>.
 
Thus, Our answer is <math>136+1=\boxed{\textbf{(C) } 137}</math>.
  
 
~seanyoon777
 
~seanyoon777
  
−
== Solution 2 ==
+
== Solution 2 (Intuitive) ==
−
(This is similar to solution 1)
+
Multiply both sides by <math>2^{17}+1</math> to get <cmath>2^{289}+1=2^{a_1} + 2^{a_2} + … + 2^{a_k} + 2^{a_1+17} + 2^{a_2+17} + … + 2^{a_k+17}.</cmath>
−
Let <math>x = 2^{17}</math>. Then, <math>2^{289} = x^{17}</math>.
+
 
−
The LHS can be rewritten as <math>\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</math>. Plugging <math>2^{17}</math> back in for <math>x</math>, we have <math>(2^{17}-1)(2^{15\cdot{17}}+2^{13\cdot{17}}+\cdots+2^{1\cdot{17}})+1=(2^{16}+2^{15}+\cdots+2^{1})(2^{15\cdot17}+2^{13\cdot17}+\cdots+2^{1\cdot17})+1</math>. When expanded, this will have <math>17\cdot8+1=137</math> terms. Therefore, our answer is <math>\boxed{\textbf{(C) } 137}</math>.
+
Notice that <math>a_1 = 0</math>, since there is a <math>1</math> on the LHS. However, now we have an extra term of <math>2^{18}</math> on the right from <math>2^{a_1+17}</math>. To cancel it, we let <math>a_2 = 18</math>. The two <math>2^{18}</math>'s now combine into a term of <math>2^{19}</math>, so we let <math>a_3 = 19</math>. And so on, until we get to <math>a_{18} = 34</math>. Now everything we don't want telescopes into <math>2^{35}</math>. We already have that term since we let <math>a_2 = 18 \implies a_2+17 = 35</math>. Everything from now on will automatically telescope to <math>2^{52}</math>. So we let <math>a_{19}</math> be <math>52</math>.
 +
 
 +
As you can see, we will have to add <math>17</math> <math>a_n</math>'s at a time, then "wait" for the sum to automatically telescope for the next <math>17</math> numbers, etc, until we get to <math>2^{289}</math>. We only need to add <math>a_n</math>'s between odd multiples of <math>17</math> and even multiples. The largest even multiple of <math>17</math> below <math>289</math> is <math>17\cdot16</math>, so we will have to add a total of <math>17\cdot 8</math> <math>a_n</math>'s. However, we must not forget we let <math>a_1=0</math> at the beginning, so our answer is <math>17\cdot8+1 = \boxed{\textbf{(C) } 137}</math>.
 +
 
 +
== Solution 3 ==
 +
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} + 1</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. ~[[User:emerald_block|emerald_block]]
 +
 
 +
==Solution 4(Fake: only use if you have no time and like losing 1.5 points)==
 +
Notice that the only answer choices that are spaced one apart are <math>136</math> and <math>137</math>. It's likely that people will forget to include the final term so the answer is <math>\boxed{137}</math>.
 +
 
 +
== Solution 5 (Similar to Solution 3) ==
 +
We can first look at smaller similar cases in binary. We can treat the initial problem as <math>\frac{2^{n^2} + 1}{2^n + 1}</math> where <math>n=17</math>. We can first look at the case <math>n=3</math> or <math>\frac{2^9 + 1}{2^3 + 1}</math>, which is equivalent to <math>\frac{1000000001_2}{1001_2}</math>. If we do long division we find that this equals <math>111001_2</math>. Then we can also look at the case <math>n=5</math> or <math>\frac{2^25+1}{2^5+1}</math>. Doing long division on this in binary gives us a quotient that is a repeating pattern of 5 zeros and 5 ones. This pattern does hold, as <math>111\text{... n ones ...}1_2 * 10\text{... n-1 zeroes ...}01_2 = (10_2)^{2n} - 1</math>. Then at the end, there is a remainder of <math>10\text{... n-1 zeroes ...}01_2</math>, which is the same as the denominator of the original fraction. Thus, for the original problem, there are <math>\frac{17-1}{2}</math> repeats of 17 zeroes and 17 ones, giving <math>8 * 17 + 1 = \boxed{\textbf{(C) }137}</math>.
 +
~Hi2937
 +
== Video Solutions ==
  
−
==Solution 3==
+
=== Video Solution 1 (Simple)===
−
Note that the expression is equal to something slightly lower than <math>2^{272}</math>. Clearly, answer choices <math>(D)</math> and <math>(E)</math> make no sense because the lowest sum for <math>273</math> terms is <math>2^{273}-1</math>. <math>(A)</math> just makes no sense. <math>(B)</math> and <math>(C)</math> are 1 apart, but because the expression is odd, it will have to contain <math>2^0=1</math>, and because <math>(C)</math> is <math>1</math> bigger, the answer is <math>\boxed{\textbf{(C) } 137}</math>.
+
https://youtu.be/f7FibYTNSm8
  
−
~Lcz
+
~Education The Study of Everything
  
−
==Video Solution==
+
=== Video Solution 2 (Richard Rusczyk)===
 +
https://artofproblemsolving.com/videos/amc/2020amc10a/511
 +
 
 +
=== Video Solution 3 ===
 +
https://www.youtube.com/watch?v=FsCOVzhjUtE&list=PLLCzevlMcsWNcTZEaxHe8VaccrhubDOlQ&index=3 ~ MathEx
 +
 
 +
=== Video Solution 4 ===
 
https://youtu.be/Ozp3k2464u4
 
https://youtu.be/Ozp3k2464u4
  
 
~IceMatrix
 
~IceMatrix
 +
 +
=== Video Solution 5 ===
 +
https://youtu.be/oDSLaQM6L1o
 +
 +
~savannahsolver
  
 
==See Also==
 
==See Also==

Latest revision as of 01:16, 5 November 2024

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} + 1$
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 like losing 1.5 points)

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}$.

Solution 5 (Similar to Solution 3)

We can first look at smaller similar cases in binary. We can treat the initial problem as $\frac{2^{n^2} + 1}{2^n + 1}$ where $n=17$. We can first look at the case $n=3$ or $\frac{2^9 + 1}{2^3 + 1}$, which is equivalent to $\frac{1000000001_2}{1001_2}$. If we do long division we find that this equals $111001_2$. Then we can also look at the case $n=5$ or $\frac{2^25+1}{2^5+1}$. Doing long division on this in binary gives us a quotient that is a repeating pattern of 5 zeros and 5 ones. This pattern does hold, as $111\text{... n ones ...}1_2 * 10\text{... n-1 zeroes ...}01_2 = (10_2)^{2n} - 1$. Then at the end, there is a remainder of $10\text{... n-1 zeroes ...}01_2$, which is the same as the denominator of the original fraction. Thus, for the original problem, there are $\frac{17-1}{2}$ repeats of 17 zeroes and 17 ones, giving $8 * 17 + 1 = \boxed{\textbf{(C) }137}$. ~Hi2937

Video Solutions

Video Solution 1 (Simple)

https://youtu.be/f7FibYTNSm8

~Education The Study of Everything

Video Solution 2 (Richard Rusczyk)

https://artofproblemsolving.com/videos/amc/2020amc10a/511

Video Solution 3

https://www.youtube.com/watch?v=FsCOVzhjUtE&list=PLLCzevlMcsWNcTZEaxHe8VaccrhubDOlQ&index=3 ~ MathEx

Video Solution 4

https://youtu.be/Ozp3k2464u4

~IceMatrix

Video Solution 5

https://youtu.be/oDSLaQM6L1o

~savannahsolver

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=231652"