Question

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$

Answer: E

Concepts:recurrences modular arithmetic

Difficulty rating: 2170

Small Hint:

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

Big Hint:

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

Solution:

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 Problem 27

Answer: E

Difficulty rating: 2170

Small Hint:

Big Hint:

Solution:

Problem 27 in Other Years