2020 AMC 8 Problems/Problem 22
Contents
[hide]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, 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 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
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
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 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
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.