2015 AMC 12B 第 20 题

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 题