Difference between revisions of "2020 AMC 8 Problems/Problem 22"
(→Solution 2) |
(→Solution 2) |
||
| Line 11: | Line 11: | ||
==Solution 2== | ==Solution 2== | ||
Start with the final output which is <math>1</math> and then work backwards, carefully including all the possible inputs that could have resulted in that output. For example, for the number <math>2</math>, if you go backwards, you only get to <math>4</math>, because <math>4</math> is the only input which can lead to an output of <math>2</math>. However, for a number like <math>16</math> for example, both the inputs <math>5</math> and <math>32</math> lead to an output of <math>16</math>. A nice way to draw this out is to make a tree diagram but one can also make a series of sets which contain all the possible inputs up to that point.<br><br> | Start with the final output which is <math>1</math> and then work backwards, carefully including all the possible inputs that could have resulted in that output. For example, for the number <math>2</math>, if you go backwards, you only get to <math>4</math>, because <math>4</math> is the only input which can lead to an output of <math>2</math>. However, for a number like <math>16</math> for example, both the inputs <math>5</math> and <math>32</math> lead to an output of <math>16</math>. A nice way to draw this out is to make a tree diagram but one can also make a series of sets which contain all the possible inputs up to that point.<br><br> | ||
| − | <math>{1}\leftarrow\{2\}\leftarrow\{4\}\leftarrow\{1,8\}\leftarrow\{2,16\}\leftarrow\{4,5,32\}\leftarrow\{1,8,10,64\}</math><br><br> | + | <math>\{1\}\leftarrow\{2\}\leftarrow\{4\}\leftarrow\{1,8\}\leftarrow\{2,16\}\leftarrow\{4,5,32\}\leftarrow\{1,8,10,64\}</math><br><br> |
The last set in this sequence contains all the numbers which will lead to the number 1 after the 6-step process is repeated. The sum of these numbers is <math>1+8+10+64=83\implies\boxed{\textbf{(E) }83}</math>.<br> | The last set in this sequence contains all the numbers which will lead to the number 1 after the 6-step process is repeated. The sum of these numbers is <math>1+8+10+64=83\implies\boxed{\textbf{(E) }83}</math>.<br> | ||
~ junaidmansuri | ~ junaidmansuri | ||
Revision as of 07:55, 18 November 2020
Contents
Problem 22
When a positive integer 
is fed into a machine, the output is a number calculated according to the rule shown below.
![[asy] size(300); defaultpen(linewidth(0.8)+fontsize(13)); real r = 0.05; draw((0.9,0)--(3.5,0),EndArrow(size=7)); filldraw((4,2.5)--(7,2.5)--(7,-2.5)--(4,-2.5)--cycle,gray(0.65)); fill(circle((5.5,1.25),0.8),white); fill(circle((5.5,1.25),0.5),gray(0.65)); fill((4.3,-r)--(6.7,-r)--(6.7,-1-r)--(4.3,-1-r)--cycle,white); fill((4.3,-1.25+r)--(6.7,-1.25+r)--(6.7,-2.25+r)--(4.3,-2.25+r)--cycle,white); fill((4.6,-0.25-r)--(6.4,-0.25-r)--(6.4,-0.75-r)--(4.6,-0.75-r)--cycle,gray(0.65)); fill((4.6,-1.5+r)--(6.4,-1.5+r)--(6.4,-2+r)--(4.6,-2+r)--cycle,gray(0.65)); label("$N$",(0.45,0)); draw((7.5,1.25)--(11.25,1.25),EndArrow(size=7)); draw((7.5,-1.25)--(11.25,-1.25),EndArrow(size=7)); label("if $N$ is even",(9.25,1.25),N); label("if $N$ is odd",(9.25,-1.25),N); label("$\frac N2$",(12,1.25)); label("$3N+1$",(12.6,-1.25)); [/asy]](http://latex.artofproblemsolving.com/e/8/7/e878d1d4459a47247d03d903a46441e85ec0a503.png)
For example, starting with an input of 
the machine will output 
Then if the output is repeatedly inserted into the machine five more times, the final output is 
![\[7 \to 22 \to 11 \to 34 \to 17 \to 52 \to 26\]](http://latex.artofproblemsolving.com/4/f/7/4f7a3ef049942c89a393ca7cf10d85cc7ddd0b8d.png)
When the same 
-step process is applied to a different starting value of 
the final output is 
What is the sum of all such integers 
![\[N \to \rule{0.5cm}{0.15mm} \to \rule{0.5cm}{0.15mm} \to \rule{0.5cm}{0.15mm} \to \rule{0.5cm}{0.15mm} \to \rule{0.5cm}{0.15mm} \to 1\]](http://latex.artofproblemsolving.com/c/8/9/c8914c251134025522a9009e8cdf1f898c2e9e08.png)
Solution 1
We see that 
work, so 
.
~yofro
Solution 2
Start with the final output which is 
and then work backwards, carefully including all the possible inputs that could have resulted in that output. For example, for the number 
, if you go backwards, you only get to 
, because is the only input which can lead to an output of . However, for a number like 
for example, both the inputs 
and 
lead to an output of . A nice way to draw this out is to make a tree diagram but one can also make a series of sets which contain all the possible inputs up to that point.
The last set in this sequence contains all the numbers which will lead to the number 1 after the 6-step process is repeated. The sum of these numbers is 
.
~ junaidmansuri
See also
| 2020 AMC 8 (Problems • Answer Key • Resources) | ||
| Preceded by Problem 21 |
Followed by Problem 23 | |
| 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 AJHSME/AMC 8 Problems and Solutions | ||
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. 
