AMC10 2019 B

AMC10 2019 B · Q25

AMC10 2019 B · Q25. It mainly tests Basic counting (rules of product/sum), Recursion & DP style counting (basic).

How many sequences of 0s and 1s of length 19 are there that begin with a 0, end with a 0, contain no two consecutive 0s, and contain no three consecutive 1s?

有长度为 19 由 0 和 1 组成的序列多少个满足：以 0 开头，以 0 结尾，不含两个连续 0，不含三个连续 1？

(A) 55 55

(B) 60 60

(D) 70 70

(E) 75 75

Answer

Correct choice: (C)

正确答案：（C）

Solution

Answer (C): For $n \ge 2$, let $a_n$ be the number of sequences of length $n$ that begin with a 0, end with a 0, contain no two consecutive 0s, and contain no three consecutive 1s. In order for the sequence to end with a 0 and satisfy the conditions, it must end either 010 or 0110. Thus $a_n = a_{n-2} + a_{n-3}$. The initial conditions for this recurrence relation are $a_2 = 0$, $a_3 = 1$ (the sequence 010), and $a_4 = 1$ (the sequence 0110). Then $a_5 = a_3 + a_2 = 1 + 0 = 1$, $a_6 = a_4 + a_3 = 1 + 1 = 2$, $a_7 = a_5 + a_4 = 1 + 1 = 2$, and so on. A bit of calculation produces the display below; $a_{19} = 65$. \[ \begin{array}{c|cccccccccc} n & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ \hline a_n & 0 & 1 & 1 & 1 & 2 & 2 & 3 & 4 & 5 & 7 \end{array} \] \[ \begin{array}{c|cccccccc} n & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 \\ \hline a_n & 9 & 12 & 16 & 21 & 28 & 37 & 49 & 65 \end{array} \]

答案（C）：对于 $n \ge 2$，令 $a_n$ 表示长度为 $n$ 的序列的个数，这些序列以 0 开头、以 0 结尾、不包含两个连续的 0，并且不包含三个连续的 1。为了使序列以 0 结尾并满足条件，其末尾必须是 010 或 0110。因此 $a_n = a_{n-2} + a_{n-3}$。该递推关系的初始条件为 $a_2 = 0$，$a_3 = 1$（序列 010），以及 $a_4 = 1$（序列 0110）。于是 $a_5 = a_3 + a_2 = 1 + 0 = 1$，$a_6 = a_4 + a_3 = 1 + 1 = 2$，$a_7 = a_5 + a_4 = 1 + 1 = 2$，等等。稍作计算可得到如下表格；$a_{19} = 65$。 \[ \begin{array}{c|cccccccccc} n & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\ \hline a_n & 0 & 1 & 1 & 1 & 2 & 2 & 3 & 4 & 5 & 7 \end{array} \] \[ \begin{array}{c|cccccccc} n & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 \\ \hline a_n & 9 & 12 & 16 & 21 & 28 & 37 & 49 & 65 \end{array} \]

Topics