Question

对每个正整数 $n$ ，令 $\operatorname{mod}_5(n)$ 表示 $n$ 除以 $5$ 的余数。递归定义函数 $f : \{0, 1, 2, 3, \ldots\}$ $\times \{0, 1, 2, 3, 4\}$ $\to \{0, 1, 2, 3, 4\}$ 如下：

$\tiny f(i, j) = \begin{cases} \operatorname{mod}_5(j + 1) & \text{当 } i = 0 \text{ 且 } 0 \le j \le 4, \\ f(i - 1, 1) & \text{当 } i \ge 1 \text{ 且 } j = 0, \text{ 且} \\ f(i - 1, f(i, j - 1)) & \text{当 } i \ge 1 \text{ 且 } 1 \le j \le 4 \end{cases}\text{。}$

$f(2015, 2)$ 是多少？

For every positive integer $n,$ let $\operatorname{mod}_5(n)$ be the remainder obtained when $n$ is divided by $5.$ Define a function $f : \{0, 1, 2, 3, \ldots\}$ $\times \{0, 1, 2, 3, 4\}$ $\to \{0, 1, 2, 3, 4\}$ recursively as follows:

$\tiny f(i, j) = \begin{cases} \operatorname{mod}_5(j + 1) & \text{if } i = 0 \text{ and } 0 \le j \le 4, \\ f(i - 1, 1) & \text{if } i \ge 1 \text{ and } j = 0, \text{ and} \\ f(i - 1, f(i, j - 1)) & \text{if } i \ge 1 \text{ and } 1 \le j \le 4. \end{cases}$

What is $f(2015, 2)?$

$0$

$1$

$2$

$3$

$4$

答案：B

知识点：递推找规律模运算

难度评级：2100

小提示：

对小的 $i$ ，逐行建立 $f(i, j)$ 的表

Build the table of $f(i, j)$ row by row for small $i$

大提示：

跟踪 $j = 2$ 这一列；当 $i$ 足够大后它会变成常数

Track the column $j = 2;$ it becomes constant once $i$ is large enough

解答：

在每一行中从左到右应用递推，得到 $\begin{array}{c|ccccc} i\backslash j&0&1&2&3&4\\ \hline 0&1&2&3&4&0\\ 1&2&3&4&0&1\\ 2&3&0&2&4&1\\ 3&0&3&4&1&0\\ 4&3&1&3&1&3\\ 5&1&1&1&1&1 \end{array}$ 如果某一行全是 $1$ ，递推就会使下一行也全是 $1$ 。因此由归纳法可知，对每个 $i\ge5$ 都有 $f(i,2)=1$ 。

因为 $2015 \ge 5$ ，所以 $f(2015, 2) = 1$ 。

因此，正确选项是 B。

Applying the recursion from left to right in each row gives $\begin{array}{c|ccccc} i\backslash j&0&1&2&3&4\\ \hline 0&1&2&3&4&0\\ 1&2&3&4&0&1\\ 2&3&0&2&4&1\\ 3&0&3&4&1&0\\ 4&3&1&3&1&3\\ 5&1&1&1&1&1 \end{array}$ If a row consists entirely of $1$ s, the recursion makes the next row entirely $1$ s as well. Hence, by induction, $f(i,2)=1$ for every $i\ge5.$

Since $2015 \ge 5,$ we get $f(2015, 2) = 1.$

Thus, the correct answer is B.

2015 AMC 12B 第 20 题

答案：B

难度评级：2100

小提示：

大提示：

解答：

其他年份的第 20 题