Question

Considera el arreglo triangular de números que tiene $0,$ $1,$ $2,$ $3,$ $\ldots$ en los lados y cuyos números interiores se obtienen sumando los dos números adyacentes de la fila anterior. Se muestran las filas $1$ a $6.$

$\begin{array}{cccccc} &&0&&&\\ &&1&1&&\\ &2&2&2&&\\ &3&4&4&3&\\ 4&7&8&7&4&\\ 5&11&15&15&11&5 \end{array}$

Sea $f(n)$ la suma de los números de la fila $n.$ ¿Cuál es el residuo al dividir $f(100)$ entre $100$ ?

Consider the triangular array of numbers with $0,$ $1,$ $2,$ $3,$ $\ldots$ along the sides and interior numbers obtained by adding the two adjacent numbers in the previous row. Rows $1$ through $6$ are shown.

$\begin{array}{cccccc} &&0&&&\\ &&1&1&&\\ &2&2&2&&\\ &3&4&4&3&\\ 4&7&8&7&4&\\ 5&11&15&15&11&5 \end{array}$

Let $f(n)$ denote the sum of the numbers in row $n.$ What is the remainder when $f(100)$ is divided by $100?$

$12$

$30$

$50$

$62$

$74$

Respuesta: E

Conceptos:recurrences aritmética modular

Nivel de dificultad: 2170

Pista pequeña:

Relaciona la suma de una fila con la anterior contando cuántas veces contribuye cada término previo

Relate a row’s sum to the previous row’s sum by counting how often each old entry contributes

Pista grande:

Resuelve la recurrencia resultante y luego calcula la potencia de $2$ módulo $100$

Solve the resulting recurrence, then compute the power of $2$ modulo $100$

Solución:

Cada término anterior contribuye a dos términos de la fila siguiente, y los dos nuevos términos de los extremos aportan un $2$ adicional. Por tanto, $f(n)=2f(n-1)+2,$ con $f(1)=0.$ Así, $f(n)=2^n-2.$ Como $2^{20}\equiv76\pmod{100}$ y $76^2\equiv76\pmod{100},$ tenemos $2^{100}\equiv76\pmod{100}.$ Por consiguiente, $f(100)\equiv74\pmod{100},$ y la respuesta correcta es E.

Every previous entry contributes to two entries of the next row, and the two new boundary entries contribute an additional $2.$ Thus $f(n)=2f(n-1)+2,$ with $f(1)=0.$ Hence $f(n)=2^n-2.$ Since $2^{20}\equiv76\pmod{100}$ and $76^2\equiv76\pmod{100},$ we have $2^{100}\equiv76\pmod{100}.$ Therefore $f(100)\equiv74\pmod{100},$ and the correct answer is E.

1995 AMC 12 Problema 27

Respuesta: E

Nivel de dificultad: 2170

Pista pequeña:

Pista grande:

Solución:

El Problema 27 en otros años