Difference between revisions of "2020 AMC 8 Problems/Problem 22"
(→Solution 1) |
(→Problem 22) |
||
Line 3: | Line 3: | ||
<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> | <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, | + | For example, startWhat>tput 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> | ||
Revision as of 16:31, 1 May 2021
Contents
Problem 22
When a positive integer is fed into a machine, the output is a number calculated according to the rule shown below.
For example, startWhat>tput is
What is the sum of all such integers
Solution 1
We start with final output of 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:
where, for example,
must come from
(as there is no integer
satisfying
), but
could come from
or
(as
, and
is even while
is odd). By construction, last set in this sequence contains all the numbers which will lead to number
to end of the
-step process, and sum is
.
Solution 2 (variant of Solution 1)
As in Solution 1, we work backwards from , this time showing the possible cases in a tree diagram:
The possible numbers are those at the "leaves" of the tree (the ends of the various branches), which are ,
,
, and
. Thus the answer is
.
Solution 3 (algebraic)
We begin by finding the inverse of the function that the machine uses. Call the input and the output
. If
is even,
, and if
is odd,
. We can therefore see that
when
is even and
when
is odd. Therefore, starting with
, if
is even,
, and if
is odd,
, but the latter is not valid since
is not actually odd. This means that the 2nd-to-last number in the sequence has to be
. Now, substituting
into the inverse formulae, if
is even,
(which is indeed even), and if
is odd,
, which is not an integer. This means the 3rd-to-last number in the sequence has to be
. Substituting in
, if
is even,
, but if
is odd,
. Both of these are valid solutions, so the 4th-to-last number can be either
or
. If it is
, then by the argument we have just made, the 5th-to-last number has to be
, the 6th-to-last number has to be
, and the 7th-to-last number, which is the first number, must be either
or
. In this way, we have ultimately found two solutions:
and
.
On the other hand, if the 4th-to-last number is , substituting
into the inverse formulae shows that the 5th-to-last number is either
or
, but the latter is not an integer. Substituting
shows that if
is even,
, but if I is odd,
, and both of these are valid. If the 6th-to-last number is
, then the first number must be
, since
is not an integer; if the 6th-to-last number is
then the first number has to be
, as
is not an integer. This means that, in total, there are
solutions for
, specifically,
,
,
, and
, which sum to
.
Video Solution by WhyMath
~savannahsolver
Video Solutions
Video Solution by Interstigation
https://youtu.be/YnwkBZTv5Fw?t=1347
~Interstigation
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.