AMC12 2007 A

AMC12 2007 A · Q25

AMC12 2007 A · Q25. It mainly tests Basic counting (rules of product/sum), Recursion & DP style counting (basic).

Call a set of integers spacy if it contains no more than one out of any three consecutive integers. How many subsets of $\{1,2,3,\ldots,12\},$ including the empty set, are spacy?

称一个整数集合为 spacy，如果它在任意三个连续整数中至多包含一个整数。$\{1,2,3,\ldots,12\}$ 的子集中（包括空集）有多少个是 spacy 的？

(A) 121 121

(B) 123 123

(D) 127 127

(E) 129 129

Answer

Correct choice: (E)

正确答案：（E）

Solution

Let $S_{n}$ denote the number of spacy subsets of $\{ 1, 2, ... n \}$. We have $S_{0} = 1, S_{1} = 2, S_{2} = 3$. The spacy subsets of $S_{n + 1}$ can be divided into two groups: - $A =$ those not containing $n + 1$. Clearly $|A|=S_{n}$. - $B =$ those containing $n + 1$. We have $|B|=S_{n - 2}$, since removing $n + 1$ from any set in $B$ produces a spacy set with all elements at most equal to $n - 2,$ and each such spacy set can be constructed from exactly one spacy set in $B$. Hence, From this recursion, we find that And so the answer is $\boxed{\textbf{(E)}129}$.

令 $S_{n}$ 表示 $\{ 1, 2, ... n \}$ 的 spacy 子集个数。则 $S_{0} = 1, S_{1} = 2, S_{2} = 3$。 $S_{n + 1}$ 的 spacy 子集可分为两类： - $A =$ 不包含 $n + 1$ 的集合。显然 $|A|=S_{n}$。 - $B =$ 包含 $n + 1$ 的集合。此时 $|B|=S_{n - 2}$，因为从 $B$ 中任取一个集合去掉 $n + 1$ 后，会得到一个所有元素都不超过 $n - 2$ 的 spacy 集合；反之，每个这样的 spacy 集合都恰对应于 $B$ 中的一个集合。因此，由该递推关系可得所以答案是 $\boxed{\textbf{(E)}129}$。

Topics