Difference between revisions of "2020 AMC 10A Problems/Problem 21"
Ihatemath123 (talk | contribs) |
|||
| (16 intermediate revisions by 8 users not shown) | |||
| Line 8: | Line 8: | ||
== Solution 1 == | == Solution 1 == | ||
First, substitute <math>2^{17}</math> with <math>x</math>. | First, substitute <math>2^{17}</math> with <math>x</math>. | ||
| − | Then, the given equation becomes <math>\frac{x^{17}+1}{x+1}=x^{16}-x^{15}+x^{14}...-x^1+x^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>x^{16}-x^{15}</math>. This equals <math>x^{15}(x-1)=x^{15} | + | 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>, | + | 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>x^{16}-x^{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>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 | + | 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>x^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>. | ||
| Line 42: | Line 42: | ||
<math>= 1\#0\#0\#0\#0\#0\#0\#0\#0\#0\#0\#0\#0\#0\#0\#0\#0\#1_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> | 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> | + | <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> | 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>\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> | ||
| Line 57: | Line 57: | ||
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]] | 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 ( | + | ==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 == | == Video Solutions == | ||
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.
Contents
Problem
There exists a unique strictly increasing sequence of nonnegative integers 
such that![\[\frac{2^{289}+1}{2^{17}+1} = 2^{a_1} + 2^{a_2} + … + 2^{a_k}.\]](http://latex.artofproblemsolving.com/2/d/6/2d6393b8673d4c77a04408bd3ea19ae955bd756f.png)
What is 
Solution 1
First, substitute 
with 
.
Then, the given equation becomes 
by sum of powers factorization.
Now consider only 
. This equals 
.
Note that 
equals 
, by difference of powers factorization (or by considering the expansion of 
).
Thus, we can see that forms the sum of 17 different powers of 2.
Applying the same method to each of 
, 
, ... , 
, we can see that each of the pairs forms the sum of 17 different powers of 2. This gives us 
.
But we must count also the 
term.
Thus, Our answer is 
.
~seanyoon777
Solution 2 (Intuitive)
Multiply both sides by 
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}.\]](http://latex.artofproblemsolving.com/0/7/8/078c3699779f590a5d2ca541465db555f99c5865.png)
Notice that 
, since there is a 
on the LHS. However, now we have an extra term of 
on the right from 
. To cancel it, we let 
. The two 's now combine into a term of 
, so we let 
. And so on, until we get to 
. Now everything we don't want telescopes into 
. We already have that term since we let 
. Everything from now on will automatically telescope to 
. So we let 
be 
.
As you can see, we will have to add 
's at a time, then "wait" for the sum to automatically telescope for the next numbers, etc, until we get to 
. We only need to add 's between odd multiples of and even multiples. The largest even multiple of below 
is 
, so we will have to add a total of 
's. However, we must not forget we let 
at the beginning, so our answer is 
.
Solution 3
In order to shorten expressions, 
will represent 
consecutive 
s when expressing numbers.
Think of the problem in binary. We have
Note that
and
Since
this means that
so
Expressing each of the pairs of the form 
in binary, we have
or
This means that each pair has terms of the form 
.
Since there are 
of these pairs, there are a total of 
terms. Accounting for the 
term, which was not in the pair, we have a total of 
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 
and 
. It's likely that people will forget to include the final term so the answer is 
.
Solution 5 (Similar to Solution 3)
We can first look at smaller similar cases in binary. We can treat the initial problem as 
where 
. We can first look at the case 
or 
, which is equivalent to 
. If we do long division we find that this equals 
. Then we can also look at the case 
or 
. 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 
. Then at the end, there is a remainder of 
, which is the same as the denominator of the original fraction. Thus, for the original problem, there are 
repeats of 17 zeroes and 17 ones, giving 
.
~Hi2937
Video Solutions
Video Solution 1 (Simple)
~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
~IceMatrix
Video Solution 5
~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. 
