Question

考察如下三角形数阵：两侧依次为 $0$ 、 $1$ 、 $2$ 、 $3$ 、 $\ldots$ ，内部每个数等于上一行相邻两个数之和。图中给出了第 $1$ 行到第 $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}$

设 $f(n)$ 表示第 $n$ 行各数之和。 $f(100)$ 除以 $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$

答案：E

知识点：recurrences 模运算

难度评级：2170

小提示：

通过统计上一行每个数在下一行中被计入的次数，建立相邻两行行和的关系

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

大提示：

解所得递推式，再计算 $2$ 的幂对 $100$ 的余数

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

解答：

上一行的每个数都会贡献给下一行的两个数，而新出现的两个边界数又额外贡献 $2$ 。因此 $f(n)=2f(n-1)+2$ ，且 $f(1)=0$ 。所以 $f(n)=2^n-2\text{。}$ 由于 $2^{20}\equiv76\pmod{100}$ ，且 $76^2\equiv76\pmod{100}$ ，可得 $2^{100}\equiv76\pmod{100}$ 。因此 $f(100)\equiv74\pmod{100}$ ，正确答案是 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 第 27 题

答案：E

难度评级：2170

小提示：

大提示：

解答：

其他年份的第 27 题