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 2)
 
(55 intermediate revisions by 25 users not shown)
Line 1: Line 1:
−
==Problem 22==
+
==Problem==
 
When a positive integer <math>N</math> is fed into a machine, the output is a number calculated according to the rule shown below.
 
When a positive integer <math>N</math> is fed into a machine, the output is a number calculated according to the rule shown below.
  
Line 5: Line 5:
 
For example, starting with an input of <math>N=7,</math> the machine will output <math>3 \cdot 7 +1 = 22.</math> Then if the output is repeatedly inserted into the machine five more times, the final output is <math>26.</math><cmath>7 \to 22 \to 11 \to 34 \to 17 \to 52 \to 26</cmath>When the same <math>6</math>-step process is applied to a different starting value of <math>N,</math> the final output is <math>1.</math> What is the sum of all such integers <math>N?</math><cmath>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</cmath>
 
For example, starting with an input of <math>N=7,</math> the machine will output <math>3 \cdot 7 +1 = 22.</math> Then if the output is repeatedly inserted into the machine five more times, the final output is <math>26.</math><cmath>7 \to 22 \to 11 \to 34 \to 17 \to 52 \to 26</cmath>When the same <math>6</math>-step process is applied to a different starting value of <math>N,</math> the final output is <math>1.</math> What is the sum of all such integers <math>N?</math><cmath>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</cmath>
 
<math>\textbf{(A) }73 \qquad \textbf{(B) }74 \qquad \textbf{(C) }75 \qquad \textbf{(D) }82 \qquad \textbf{(E) }83</math>
 
<math>\textbf{(A) }73 \qquad \textbf{(B) }74 \qquad \textbf{(C) }75 \qquad \textbf{(D) }82 \qquad \textbf{(E) }83</math>
 +
 
==Solution 1==
 
==Solution 1==
−
We see that <math>1,8,10,64</math> work, so <math>\boxed{\textbf{(E) }83}</math>.
+
We start with final output of <math>1</math> and work backward, taking cares to consider all possible inputs that could have resulted in any particular output. This produces following set of possibilities each stage:
−
~yofro
+
<cmath>\{1\}\rightarrow\{2\}\rightarrow\{4\}\rightarrow\{1,8\}\rightarrow\{2,16\}\rightarrow\{4,5,32\}\rightarrow\{1,8,10,64\}</cmath>
 +
where, for example, <math>2</math> must come from <math>4</math> (as there is no integer <math>n</math> satisfying <math>3n+1=2</math>), but <math>16</math> could come from <math>32</math> or <math>5</math> (as <math>\frac{32}{2} = 3 \cdot 5 + 1 = 16</math>, and <math>32</math> is even while <math>5</math> is odd). By construction, last set in this sequence contains all the numbers which will lead to number <math>1</math> to end of the <math>6</math>-step process, and sum is <math>1+8+10+64=\boxed{\textbf{(E) }83}</math>.
 +
 
 +
==Solution 2 (variant of Solution 1)==
 +
As in Solution 1, we work backwards from <math>1</math>, this time showing the possible cases in a tree diagram:
 +
 
 +
<asy>
 +
// Upper branches
 +
draw((-6, 1.5)--(-5, 1)--(-3, 1)--(-2,0)--(0, 0));
 +
draw((-6, 0.5)--(-5, 1));
 +
// Lower branches
 +
draw((-6, -1.5)--(-5, -1.5)--(-4, -1)--(-3, -1)--(-2, 0));
 +
draw((-6, -0.5)--(-5, -0.5)--(-4, -1));
 +
 
 +
label("$1$", (0, 0),  UnFill(0.1mm));
 +
label("$2$", (-1, 0), UnFill(0.1mm));
 +
label("$4$", (-2, 0), UnFill(0.1mm));
 +
 
 +
// Upper branches
 +
label("$1$", (-3, 1), UnFill(0.1mm));
 +
label("$2$", (-4, 1), UnFill(0.1mm));
 +
label("$4$", (-5, 1), UnFill(0.1mm));
 +
label("$\textbf{8}$", (-6, 1.5), UnFill(0.1mm));
 +
label("$\textbf{1}$", (-6, 0.5), UnFill(0.1mm));
 +
 
 +
// Lower branches
 +
label("$8$", (-3, -1), UnFill(0.1mm));
 +
label("$16$",(-4, -1), UnFill(0.1mm));
 +
label("$5$", (-5, -0.5), UnFill(0.1mm));
 +
label("$32$", (-5, -1.5), UnFill(0.1mm));
 +
label("$\textbf{10}$", (-6, -0.5), UnFill(0.1mm));
 +
label("$\textbf{64}$", (-6, -1.5), UnFill(0.1mm));
 +
</asy>
 +
 
 +
The possible numbers are those at the "leaves" of the tree (the ends of the various branches), which are <math>1</math>, <math>8</math>, <math>64</math>, and <math>10</math>. Thus the answer is <math>1+8+64+10=\boxed{\textbf{(E) }83}</math>.
 +
 
 +
==Solution 3 (algebraic)==
 +
We begin by finding 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>. We can therefore see that <math>I=2O</math> when <math>I</math> is even and <math>I=\frac{O-1}{3}</math> when <math>I</math> is odd. Therefore, starting with <math>1</math>, if <math>I</math> is even, <math>I=2</math>, and if <math>I</math> is odd, <math>I=0</math>, but the latter is not valid since <math>0</math> is not actually odd. This means that the 2nd-to-last number in the sequence has to be <math>2</math>. Now, substituting <math>2</math> into the inverse formulae, if <math>I</math> is even, <math>I=4</math> (which is indeed even), and if <math>I</math> is odd, <math>I=\frac{1}{3}</math>, which is not an integer. This means the 3rd-to-last number in the sequence has to be <math>4</math>. Substituting in <math>4</math>, if <math>I</math> is even, <math>I=8</math>, but if <math>I</math> is odd, <math>I=1</math>. Both of these are valid solutions, so the 4th-to-last number can be either <math>1</math> or <math>8</math>. If it is <math>1</math>, then by the argument we have just made, 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, which is the first number, must be either <math>1</math> or <math>8</math>. In this way, we have ultimately found two solutions: <math>N=1</math> and <math>N=8</math>.
 +
 
 +
On the other hand, if the 4th-to-last number is <math>8</math>, substituting <math>8</math> into the inverse formulae shows that the 5th-to-last number is either <math>16</math> or <math>\frac{7}{3}</math>, but the latter is not an integer. Substituting <math>16</math> shows that if <math>I</math> is even, <math>I=32</math>, but if I is odd, <math>I=5</math>, and both of these are valid. If the 6th-to-last number is <math>32</math>, then the first number must be <math>64</math>, since <math>\frac{31}{3}</math> is not an integer; if the 6th-to-last number is <math>5,</math> then the first number has to be <math>10</math>, as <math>\frac{4}{3}</math> is not an integer. This means that, in total, there are <math>4</math> solutions for <math>N</math>, specifically, <math>1</math>, <math>8</math>, <math>10</math>, and <math>64</math>, which sum to <math>\boxed{\textbf{(E) }83}</math>.
 +
 
 +
==Remark==
 +
This function is known as the Collatz conjecture stating that every counting number (<math>1</math>, <math>2</math>, <math>3</math>, <math>4</math>, <math>...</math>) will eventually output the sequence (<math>4</math>, <math>2</math>, <math>1</math>, <math>4</math>, <math>2</math>, <math>1</math>, <math>...</math>) if put through the function enough times. It is an unsolved conjecture but has been tested by brute force for every starting number up to <math>2^{68}</math>.
 +
 
 +
==Video Solution by Math-X (First understand the problem!!!)==
 +
https://youtu.be/UnVo6jZ3Wnk?si=l0KAetejsLeFS2We&t=4703
 +
 
 +
~Math-X
 +
 
 +
==Video Solution (🚀 Just 2 min 🚀)==
 +
https://youtu.be/fEux4gUZFbM
 +
 
 +
~<i>Education, the Study of Everything</i>
 +
 
 +
==Video Solution==
 +
https://youtu.be/Tf_80QNGmsI
 +
 
 +
Please like and subscribe!
 +
 
 +
== Video Solution by OmegaLearn ==
 +
https://youtu.be/ytTRdD-LVlo?t=755
 +
 
 +
~ pi_is_3.14
 +
 
 +
==Video Solution==
 +
 
 +
https://www.youtube.com/watch?v=tItOXq9kvu4  ~David
 +
 
 +
==Video Solution by Mathiscool==
 +
 
 +
https://www.youtube.com/watch?v=aLq7LrZZGhc
 +
 
  
−
==Solution 2==
+
==Video Solution by WhyMath==
−
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>
+
https://youtu.be/ZrDCymOhDdI
−
<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>
 
−
~[http://artofproblemsolving.com/community/user/jmansuri junaidmansuri]
 
  
−
==Solution 3==
+
~savannahsolver
  
−
The most straightforward solutions is just working backwards with a diagram as shown below:
+
==Video Solutions==
 +
https://youtu.be/lhDFmiKNPBg ~ The Learning Royal
  
−
<img>https://services.artofproblemsolving.com/download.php?id=YXR0YWNobWVudHMvZC8yLzc0MjY0Yjc2NDcyMDgwNTBlZDlhMDlmNjNmMjI1Y2RhNmUwODkyLnBuZw==&rn=MjAyMCBBTUMgOCBTb2x1dGlvbiAyMi5wbmc=</img>
+
==Video Solution by Interstigation==
 +
https://youtu.be/YnwkBZTv5Fw?t=1347
  
 +
~Interstigation
  
−
Hence, the answer is <math>1+8+64+10=\textbf{(E) }83</math>.
+
==Video Solution by STEMbreezy==
 +
https://youtu.be/wq8EUCe5oQU?t=83
  
−
-franzliszt
+
~STEMbreezy
 +
==Note==
  
−
==Solution 4 (Basically the same solution but in detail)==
+
This problem is related to a famous unsolved problem, the Collatz Conjecture, also known as the Hailstone Problem, which essentially asks whether or not integer <math>n</math>, repeatedly put in the machine arbitrarily many times, will eventually reach <math>1</math>.
−
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
 
−
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}}

Latest revision as of 10:17, 12 December 2023

Problem

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 start with final output of $1$ and work backward, taking cares to consider all possible inputs that could have resulted in any particular output. This produces following set of possibilities each stage: \[\{1\}\rightarrow\{2\}\rightarrow\{4\}\rightarrow\{1,8\}\rightarrow\{2,16\}\rightarrow\{4,5,32\}\rightarrow\{1,8,10,64\}\] where, for example, $2$ must come from $4$ (as there is no integer $n$ satisfying $3n+1=2$), but $16$ could come from $32$ or $5$ (as $\frac{32}{2} = 3 \cdot 5 + 1 = 16$, and $32$ is even while $5$ is odd). By construction, last set in this sequence contains all the numbers which will lead to number $1$ to end of the $6$-step process, and sum is $1+8+10+64=\boxed{\textbf{(E) }83}$.

Solution 2 (variant of Solution 1)

As in Solution 1, we work backwards from $1$, this time showing the possible cases in a tree diagram:

[asy] // Upper branches draw((-6, 1.5)--(-5, 1)--(-3, 1)--(-2,0)--(0, 0)); draw((-6, 0.5)--(-5, 1)); // Lower branches draw((-6, -1.5)--(-5, -1.5)--(-4, -1)--(-3, -1)--(-2, 0)); draw((-6, -0.5)--(-5, -0.5)--(-4, -1)); label("$1$", (0, 0), UnFill(0.1mm)); label("$2$", (-1, 0), UnFill(0.1mm)); label("$4$", (-2, 0), UnFill(0.1mm)); // Upper branches label("$1$", (-3, 1), UnFill(0.1mm)); label("$2$", (-4, 1), UnFill(0.1mm)); label("$4$", (-5, 1), UnFill(0.1mm)); label("$\textbf{8}$", (-6, 1.5), UnFill(0.1mm)); label("$\textbf{1}$", (-6, 0.5), UnFill(0.1mm)); // Lower branches label("$8$", (-3, -1), UnFill(0.1mm)); label("$16$",(-4, -1), UnFill(0.1mm)); label("$5$", (-5, -0.5), UnFill(0.1mm)); label("$32$", (-5, -1.5), UnFill(0.1mm)); label("$\textbf{10}$", (-6, -0.5), UnFill(0.1mm)); label("$\textbf{64}$", (-6, -1.5), UnFill(0.1mm)); [/asy]

The possible numbers are those at the "leaves" of the tree (the ends of the various branches), which are $1$, $8$, $64$, and $10$. Thus the answer is $1+8+64+10=\boxed{\textbf{(E) }83}$.

Solution 3 (algebraic)

We begin by finding 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$. We can therefore see that $I=2O$ when $I$ is even and $I=\frac{O-1}{3}$ when $I$ is odd. Therefore, starting with $1$, if $I$ is even, $I=2$, and if $I$ is odd, $I=0$, but the latter is not valid since $0$ is not actually odd. This means that the 2nd-to-last number in the sequence has to be $2$. Now, substituting $2$ into the inverse formulae, if $I$ is even, $I=4$ (which is indeed even), and if $I$ is odd, $I=\frac{1}{3}$, which is not an integer. This means the 3rd-to-last number in the sequence has to be $4$. Substituting in $4$, if $I$ is even, $I=8$, but if $I$ is odd, $I=1$. Both of these are valid solutions, so the 4th-to-last number can be either $1$ or $8$. If it is $1$, then by the argument we have just made, the 5th-to-last number has to be $2$, the 6th-to-last number has to be $4$, and the 7th-to-last number, which is the first number, must be either $1$ or $8$. In this way, we have ultimately found two solutions: $N=1$ and $N=8$.

On the other hand, if the 4th-to-last number is $8$, substituting $8$ into the inverse formulae shows that the 5th-to-last number is either $16$ or $\frac{7}{3}$, but the latter is not an integer. Substituting $16$ shows that if $I$ is even, $I=32$, but if I is odd, $I=5$, and both of these are valid. If the 6th-to-last number is $32$, then the first number must be $64$, since $\frac{31}{3}$ is not an integer; if the 6th-to-last number is $5,$ then the first number has to be $10$, as $\frac{4}{3}$ is not an integer. This means that, in total, there are $4$ solutions for $N$, specifically, $1$, $8$, $10$, and $64$, which sum to $\boxed{\textbf{(E) }83}$.

Remark

This function is known as the Collatz conjecture stating that every counting number ($1$, $2$, $3$, $4$, $...$) will eventually output the sequence ($4$, $2$, $1$, $4$, $2$, $1$, $...$) if put through the function enough times. It is an unsolved conjecture but has been tested by brute force for every starting number up to $2^{68}$.

Video Solution by Math-X (First understand the problem!!!)

https://youtu.be/UnVo6jZ3Wnk?si=l0KAetejsLeFS2We&t=4703

~Math-X

Video Solution (🚀 Just 2 min 🚀)

https://youtu.be/fEux4gUZFbM

~Education, the Study of Everything

Video Solution

https://youtu.be/Tf_80QNGmsI

Please like and subscribe!

Video Solution by OmegaLearn

https://youtu.be/ytTRdD-LVlo?t=755

~ pi_is_3.14

Video Solution

https://www.youtube.com/watch?v=tItOXq9kvu4 ~David

Video Solution by Mathiscool

https://www.youtube.com/watch?v=aLq7LrZZGhc


Video Solution by WhyMath

https://youtu.be/ZrDCymOhDdI

~savannahsolver

Video Solutions

https://youtu.be/lhDFmiKNPBg ~ The Learning Royal

Video Solution by Interstigation

https://youtu.be/YnwkBZTv5Fw?t=1347

~Interstigation

Video Solution by STEMbreezy

https://youtu.be/wq8EUCe5oQU?t=83

~STEMbreezy

Note

This problem is related to a famous unsolved problem, the Collatz Conjecture, also known as the Hailstone Problem, which essentially asks whether or not integer $n$, repeatedly put in the machine arbitrarily many times, will eventually reach $1$.

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