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 8 Problems/Problem 22"

(→‎Solution 3)
(→‎Solution 4 (Basically the same solution but in detail))
Line 26: Line 26:
  
 
==Solution 4 (Basically the same solution but in detail)==
 
==Solution 4 (Basically the same solution but in detail)==
−
To solve this, we can work backward. First, we find the inverse of the function that the machine uses. Call the input I and the output O. If I is even, O=I/2, and if I is odd, O=3I+1. This means the inverse formulas are I=2O when I is even and I=(O-1)/3 when I is odd. From here, we can plug in 1 into both of these equations to find out what values of I lead to an O value of 1. If I is even, I=2, and if I is odd, I=0. Note that I=0 is not a valid solution, since 0 is not odd. This means that the second to last number in the sequence has to be 2 in order for the last number to be 1. Next, plug in 2 into each of these equations. If I is even, I=4, and if I is odd, I=1/3. Once again, 1/3 is not valid, since it has to be a positive integer, but 4 works. This means the 3rd-to-last number in the sequence has to be 4. Now comes the first split: if I is even, I=8, but if I is odd, I=1. This means the 4th-to-last number can be either 1 or 8. If it is 1, following the same logic from before, the 5th-to-last number has to be 2, the 6th-to-last number has to be 4, and the 7th-to-last number, or the first number, has to be either 1 or 8. This gives us 2 solutions: N=1, or N=8. If the 4th-to-last number is 8, that  
+
To solve this, we can work backward. First, we find the inverse of the function that the machine uses. Call the input <math>I</math> and the output <math>O.</math> If <math>I</math> is even, <math>O=\frac{I}{2},</math> and if <math>I</math> is odd, <math>O=3I+1.</math> This means the inverse formulas are <math>I=2O</math> when <math>I</math> is even and <math>I=\frac{O-1}{3}</math> when <math>I</math> is odd. From here, we can plug in <math>1</math> into both of these equations to find out what values of <math>I</math> lead to an <math>O</math> value of <math>1.</math> If <math>I</math> is even, <math>I=2,</math> and if <math>I</math> is odd, <math>I=0.</math> Note that <math>I=0</math> is not a valid solution, since <math>0</math> is not odd. This means that the second to last number in the sequence has to be <math>2</math> in order for the last number to be <math>1.</math> Next, plug in <math>2</math> into each of these equations. If <math>I</math> is even, <math>I=4,</math> and if <math>I</math> is odd, <math>I=\frac{1}{3}.</math> Once again, <math>\frac{1}{3}</math> is not valid, since it has to be a positive integer, but <math>4</math> works. This means the 3rd-to-last number in the sequence has to be <math>4.</math> Now comes the first split: if <math>I</math> is even, <math>I=8,</math> but if <math>I</math> is odd, <math>I=1.</math> This means the 4th-to-last number can be either <math>1</math> or <math>8.</math> If it is <math>1,</math> following the same logic from before, the 5th-to-last number has to be <math>2,</math> the 6th-to-last number has to be <math>4,</math> and the 7th-to-last number, or the first number, has to be either <math>1</math> or <math>8.</math> This gives us <math>2</math> solutions: <math>N=1,</math> or <math>N=8.</math> If the 4th-to-last number is <math>8,</math> that means the 5th-to-last number is either <math>16</math> or <math>\frac{7}{3}.</math> But <math>\frac{7}{3}</math> doesn't work, so it has to be <math>16.</math> Now we run into another split: if <math>I</math> is even, <math>I=32,</math> but if I is odd, <math>I=5.</math> If the 6th-to-last number is <math>32,</math> the 7th-to-last one, <math>N,</math> has to be <math>64,</math> since <math>\frac{31}{2}</math> doesn't work, and if the 6th-to-last number is <math>5,</math> then <math>N=10.</math> This means that there are <math>4</math> solutions for <math>N:</math> <math>1, 8, 10, and 64,</math> and their sum is <math>83.</math> -theepiccarrot7
−
means the 5th-to-last number is either 16 or 7/3. 7/3 doesn't work, so it has to be 16. Now we run into another split: if I is even, I=32, but if I is odd, I=5. If the 6th-to-last number is 32, the 7th-to-last one, N, has to be 64, since 31/2 doesn't work, and if the 6th-to-last number is 5, N=10. This means that there are 4 solutions for N, 1, 8, 10, and 64, and their sum is 83. -theepiccarrot7
 
  
 
==See also==  
 
==See also==  
 
{{AMC8 box|year=2020|num-b=21|num-a=23}}
 
{{AMC8 box|year=2020|num-b=21|num-a=23}}
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 21:15, 19 November 2020

Problem 22

When a positive integer $N$ 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] For example, starting with an input of $N=7,$ the machine will output $3 \cdot 7 +1 = 22.$ Then if the output is repeatedly inserted into the machine five more times, the final output is $26.$\[7 \to 22 \to 11 \to 34 \to 17 \to 52 \to 26\]When the same $6$-step process is applied to a different starting value of $N,$ the final output is $1.$ What is the sum of all such integers $N?$\[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\] $\textbf{(A) }73 \qquad \textbf{(B) }74 \qquad \textbf{(C) }75 \qquad \textbf{(D) }82 \qquad \textbf{(E) }83$

Solution 1

We see that $1,8,10,64$ work, so $\boxed{\textbf{(E) }83}$. ~yofro

Solution 2

Start with the final output which is $1$ and then work backwards, carefully including all the possible inputs that could have resulted in that output. For example, for the number $2$, if you go backwards, you only get to $4$, because $4$ is the only input which can lead to an output of $2$. However, for a number like $16$ for example, both the inputs $5$ and $32$ lead to an output of $16$. 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.

$\{1\}\leftarrow\{2\}\leftarrow\{4\}\leftarrow\{1,8\}\leftarrow\{2,16\}\leftarrow\{4,5,32\}\leftarrow\{1,8,10,64\}$

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 $1+8+10+64=83\implies\boxed{\textbf{(E) }83}$.
~junaidmansuri

Solution 3

The most straightforward solutions is just working backwards with a diagram as shown below:

https://services.artofproblemsolving.com/download.php?id=YXR0YWNobWVudHMvZC8yLzc0MjY0Yjc2NDcyMDgwNTBlZDlhMDlmNjNmMjI1Y2RhNmUwODkyLnBuZw==&rn=MjAyMCBBTUMgOCBTb2x1dGlvbiAyMi5wbmc=

Hence, the answer is $1+8+64+10=\textbf{(E) }83$.

-franzliszt

Solution 4 (Basically the same solution but in detail)

To solve this, we can work backward. First, we find the inverse of the function that the machine uses. Call the input $I$ and the output $O.$ If $I$ is even, $O=\frac{I}{2},$ and if $I$ is odd, $O=3I+1.$ This means the inverse formulas are $I=2O$ when $I$ is even and $I=\frac{O-1}{3}$ when $I$ is odd. From here, we can plug in $1$ into both of these equations to find out what values of $I$ lead to an $O$ value of $1.$ If $I$ is even, $I=2,$ and if $I$ is odd, $I=0.$ Note that $I=0$ is not a valid solution, since $0$ is not odd. This means that the second to last number in the sequence has to be $2$ in order for the last number to be $1.$ Next, plug in $2$ into each of these equations. If $I$ is even, $I=4,$ and if $I$ is odd, $I=\frac{1}{3}.$ Once again, $\frac{1}{3}$ is not valid, since it has to be a positive integer, but $4$ works. This means the 3rd-to-last number in the sequence has to be $4.$ Now comes the first split: if $I$ is even, $I=8,$ but if $I$ is odd, $I=1.$ This means the 4th-to-last number can be either $1$ or $8.$ If it is $1,$ following the same logic from before, the 5th-to-last number has to be $2,$ the 6th-to-last number has to be $4,$ and the 7th-to-last number, or the first number, has to be either $1$ or $8.$ This gives us $2$ solutions: $N=1,$ or $N=8.$ If the 4th-to-last number is $8,$ that means the 5th-to-last number is either $16$ or $\frac{7}{3}.$ But $\frac{7}{3}$ doesn't work, so it has to be $16.$ Now we run into another split: if $I$ is even, $I=32,$ but if I is odd, $I=5.$ If the 6th-to-last number is $32,$ the 7th-to-last one, $N,$ has to be $64,$ since $\frac{31}{2}$ doesn't work, and if the 6th-to-last number is $5,$ then $N=10.$ This means that there are $4$ solutions for $N:$ $1, 8, 10, and 64,$ and their sum is $83.$ -theepiccarrot7

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. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2020_AMC_8_Problems/Problem_22&oldid=137901"