Question

当一个正整数 $N$ 输入机器时，输出按下图规则计算。

例如，输入 $N=7$ 时，机器输出 $3 \cdot 7 + 1 = 22$ 。然后把输出再连续输入机器五次，最终输出为 $26$ ： $\begin{align*} &7 \to 22 \to 11 \to 34 \\ &\to 17 \to 52 \to 26 \end{align*}$ 对另一个起始值 $N$ 应用同样的 $6$ 步过程，最终输出为 $1$ 。所有这样的整数 $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*}$

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$

答案：E

知识点：逆推法树状图

难度评级：1670

小提示：

从最终输出 $1$ 倒推

Work backward from the final output $1$

大提示：

前一个值总可以是 $2m$ ，有时也可以是 $\frac{m-1}{3}$

A previous value can be $2m$ , and sometimes $\frac{m-1}{3}$

视频讲解：

Click to load, then click again to play

文字解答：

从 $1$ 倒推。一个值 $m$ 总可以由偶数输入 $2m$ 产生；当 $\frac{m-1}{3}$ 是正奇数时，也可以由这个奇数输入产生。

列出每次倒推后所有可能的值： $\begin{aligned} \{1\}&\leftarrow\{2\}\leftarrow\{4\}\leftarrow\{1,8\}\\ &\leftarrow\{2,16\}\leftarrow\{4,5,32\}\\ &\leftarrow\{1,8,10,64\}\text{。} \end{aligned}$ 因此可能的起始值为 $1$ 、 $8$ 、 $10$ 和 $64$ ，它们的和是 $83$ 。

正确答案是 E。

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.

2020 AMC 8 第 22 题