2015 AMC 12B Problema 20

Question

Para cada entero positivo

n,

sea

\operatorname{mod}_5(n)

el residuo obtenido al dividir

n

entre

5.

Define una función

f : \{0, 1, 2, 3, \ldots\}

\times \{0, 1, 2, 3, 4\}

\to \{0, 1, 2, 3, 4\}

recursivamente como sigue:

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

¿Cuánto es

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

Respuesta: B

Conceptos:recursión reconocimiento de patrones aritmética modular

Nivel de dificultad: 2100

Pista pequeña:

Construye la tabla de

f(i, j)

fila por fila para

i

pequeño

Build the table of

f(i, j)

row by row for small

i

Pista grande:

Sigue la columna

j = 2;

se vuelve constante cuando

i

es lo suficientemente grande

Track the column

j = 2;

it becomes constant once

i

is large enough

Solución:

Aplicar la recursión de izquierda a derecha en cada fila da

\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}

Si una fila está formada enteramente por

1

, la recursión hace que la fila siguiente también esté formada enteramente por

1

. Por lo tanto, por inducción,

f(i,2)=1

para todo

i\ge5.

Como

2015 \ge 5,

obtenemos

f(2015, 2) = 1.

Por lo tanto, la respuesta correcta es 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.