2020 AMC 8 Problems/Problem 22
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
Solution 3
The most straightforward solutions is just working backwards with a diagram as shown below:
Hence, the answer is 
.
-franzliszt
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. 
