Question

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

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?

$121$

$123$

$125$

$127$

$129$

答案：E

知识点：递推计数子集

难度评级：2240

小提示：

设 $c_n$ 表示 $\{1,\ldots,n\}$ 的稀疏子集个数；按是否包含 $n$ 分类。

Let $c_n$ count the spacy subsets of $\{1,\ldots,n\}$ ; condition on whether $n$ is included

大提示：

不包含 $n$ 有 $c_{n-1}$ 种；包含它会禁止 $n-1,n-2$ 有 $c_{n-3}$ 种，所以 $c_n=c_{n-1}+c_{n-3}$ 。

Excluding $n$ gives $c_{n-1}$ ; including it forbids $n-1,n-2,$ giving $c_{n-3},$ so $c_n=c_{n-1}+c_{n-3}$

解答：

设 $c_n$ 为 $\{1,\ldots,n\}$ 的稀疏子集个数。一个稀疏子集要么不包含 $n$ （有 $c_{n-1}$ 种），要么包含 $n$ ，此时它不能包含 $n-1$ 和 $n-2$ （有 $c_{n-3}$ 种）。

因此 $c_n=c_{n-1}+c_{n-3}$ ，且 $c_1=2$ ， $c_2=3$ ， $c_3=4$ 。

这个数列继续为 $6,9,13,19,28,41,60,88,129$ ，所以 $c_{12}=129$ 。

因此，正确答案是 E。

Let $c_n$ be the number of spacy subsets of $\{1,\ldots,n\}.$ A spacy subset either omits $n$ (there are $c_{n-1}$ of these) or contains $n,$ in which case it omits $n-1$ and $n-2$ (there are $c_{n-3}$ of these).

Hence $c_n=c_{n-1}+c_{n-3},$ with $c_1=2,$ $c_2=3,$ $c_3=4.$

The sequence continues $6,9,13,19,28,41,60,88,129,$ so $c_{12}=129.$

Thus, the correct answer is E.

2007 AMC 12A 第 25 题

答案：E

难度评级：2240

小提示：

大提示：

解答：

其他年份的第 25 题