2020 AMC 8

Complete problem set with solutions and individual problem pages

Problem 22 Hard

When a positive integer N is fed into a machine, the output is a number calculated according to the rule shown below.

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

  • A.

    73

  • B.

    74

  • C.

    75

  • D.

    82

  • E.

    83

Answer:E

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}.

Related Problems
Problem 20 2020 AMC 8
Problem 21 2020 AMC 8
Problem 23 2020 AMC 8
Problem 24 2020 AMC 8
Think Academy Powered by ChatGPT