2020 AMC 8 Problem 22

Question

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.

\begin{align*} &7 \to 22 \to 11 \to 34 \\ &\to 17 \to 52 \to 26 \end{align*}

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?

\begin{align*} &N \to \underline{\phantom{00}} \to \underline{\phantom{00}} \to \underline{\phantom{00}}\\ &\to \underline{\phantom{00}} \to \underline{\phantom{00}} \to 1 \end{align*}

73

74

75

82

83

Work backward from the final output

1

A previous value can be

2m

, and sometimes

\frac{m-1}{3}

Click to load, then click again to play

Work backward from

1.

A value

m

can always come from the even input

2m.

It can also come from the odd input

\frac{m-1}{3}

when that expression is a positive odd integer.

Listing the possible values after each backward step gives

\begin{aligned} \{1\}&\leftarrow\{2\}\leftarrow\{4\}\leftarrow\{1,8\}\\ &\leftarrow\{2,16\}\leftarrow\{4,5,32\}\\ &\leftarrow\{1,8,10,64\}. \end{aligned}

Thus the possible starting values are

1,

8,

10,

64,

whose sum is

83.

Thus, the correct answer is E.

Problem 22 in other years