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"

(Removed solutions which either gave no proof or were essentially the same as each other, and improved clarity and formatting)
 
(50 intermediate revisions by 23 users not shown)
Line 7: Line 7:
  
 
==Solution 1==
 
==Solution 1==
−
We start with the final output of <math>1</math> and work backwards, taking care to consider all possible inputs that could have resulted in any particular output. This produces the following set of possibilities at each stage:
+
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:
−
<cmath>\{1\}\leftarrow\{2\}\leftarrow\{4\}\leftarrow\{1,8\}\leftarrow\{2,16\}\leftarrow\{4,5,32\}\leftarrow\{1,8,10,64\}</cmath>
+
<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> with <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, the last set in this sequence contains all the numbers which will lead to the number <math>1</math> at the end of the <math>6</math>-step process, and their sum is <math>1+8+10+64=\boxed{\textbf{(E) }83}</math>.
+
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)==
 
==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:
 
As in Solution 1, we work backwards from <math>1</math>, this time showing the possible cases in a tree diagram:
−
[[File:Prob22-diagram.png|middle|center]]
+
 
 +
<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>.
 
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>.
  
Line 20: Line 48:
  
 
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>.
 
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
 +
 +
 +
==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 <math>n</math>, repeatedly put in the machine arbitrarily many times, will eventually reach <math>1</math>.
  
 
==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"