2015 AMC 12B Problem 20

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)?

Show solution

Solution

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.

Tagged: recursion · pattern recognition · modular arithmetic