AMC12 2002 A

AMC12 2002 A · Q21

AMC12 2002 A · Q21. It mainly tests Recursion & DP style counting (basic), Sequences in number theory (remainders patterns).

Consider the sequence of numbers: $4,7,1,8,9,7,6,\dots$ For $n>2$, the $n$-th term of the sequence is the units digit of the sum of the two previous terms. Let $S_n$ denote the sum of the first $n$ terms of this sequence. The smallest value of $n$ for which $S_n>10,000$ is:

考虑数列：$4,7,1,8,9,7,6,\dots$。对于 $n>2$，该数列的第 $n$ 项是前两项之和的个位数。设 $S_n$ 表示该数列前 $n$ 项的和。使得 $S_n>10,000$ 的最小 $n$ 是：

(A) 1992 1992

(B) 1999 1999

(D) 2002 2002

(E) 2004 2004

Answer

Correct choice: (B)

正确答案：（B）

Solution

The sequence is infinite. As there are only $100$ pairs of digits, sooner or later a pair of consecutive digits will occur for the second time. As each next digit only depends on the previous two, from this point on the sequence will be periodic. (Additionally, as every two consecutive digits uniquely determine the previous one as well, the first pair of digits that will occur twice must be the first pair $4,7$.) Hence it is a good idea to find the period. Writing down more terms of the sequence, we get: \[4,7,1,8,9,7,6,3,9,2,1,3,4,7,\dots\] and we found the period. The length of the period is $12$, and its sum is $4+7+\cdots+1+3 = 60$. Hence for each $k$ we have $S_{12k} = 60k$. We have $\lfloor 10000/60 \rfloor = 166$ and $166\cdot 12 = 1992$, therefore $S_{1992} = 60\cdot 166 = 9960$. The rest can now be computed by hand, we get $S_{1998} = 9960+4+7+1+8+9+7= 9996$, and $S_{1999}=9996 + 6 = 10002$, thus the answer is $\boxed{\text{(B) }1999}$.

该数列是无限的。由于只有 $100$ 种两位数字对，迟早会有一对相邻数字第二次出现。又因为每一项只依赖于前两项，从这一点开始数列将呈周期性。（另外，由于任意相邻两项也唯一确定前一项，因此第一次重复出现的相邻数字对必然是最初的那一对 $4,7$。）因此，找出周期是个好主意。继续写出更多项，得到： \[4,7,1,8,9,7,6,3,9,2,1,3,4,7,\dots\] 于是找到了周期。周期长度为 $12$，其和为 $4+7+\cdots+1+3 = 60$。因此对每个 $k$ 都有 $S_{12k} = 60k$。有 $\lfloor 10000/60 \rfloor = 166$ 且 $166\cdot 12 = 1992$，因此 $S_{1992} = 60\cdot 166 = 9960$。接下来手算剩余部分：$S_{1998} = 9960+4+7+1+8+9+7= 9996$，并且 $S_{1999}=9996 + 6 = 10002$，因此答案是 $\boxed{\text{(B) }1999}$。

Topics