2007 AMC 12A 第 25 题

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 题