2020 AMC 8 Problems/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
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 .
This function is known as the Collatz conjecture stating that every counting number (, , , , ) will eventually output the sequence (, , , , , , ) 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 .
Video Solution by Mathiscool
Video Solution by WhyMath
https://youtu.be/lhDFmiKNPBg ~ The Learning Royal
Video Solution by Interstigation
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 , repeatedly put in the machine arbitrarily many times, will eventually reach .
|2020 AMC 8 (Problems • Answer Key • Resources)|
|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|