2006 AMC 12A 第 25 题

Question

\{1, 2, 3, \ldots, 15\}

有多少个非空子集

S

满足以下两个性质？

(1)

S

中没有两个连续整数。

(2)

若

S

含有

k

个元素，则

S

不含任何小于

k

的数。

How many non-empty subsets

S

of

\{1, 2, 3, \ldots, 15\}

have the following two properties?

(1)

No two consecutive integers belong to

S.

(2)

If

S

contains

k

elements, then

S

contains no number less than

k.

277

311

376

377

405

答案：E

知识点：子集双射组合

难度评级：2550

小提示：

一个有效的

k

-元素集合是

\{k, k+1, \ldots, 15\}

中的一个

k

-子集，且没有两个连续元素。

A

k

-element valid set is a

k

-subset of

\{k, k+1, \ldots, 15\}

with no two consecutive

大提示：

这样的集合与一个

(17 - 2k)

-元素集合的

k

-子集一一对应，数量为

\binom{17 - 2k}{k}

。

Such sets biject with

k

-subsets of a

(17 - 2k)

-element set, counted by

\binom{17 - 2k}{k}

解答：

由性质

(2)

，一个有效的

k

-元素集合是

\{k, k+1, \ldots, 15\}

的一个

k

-子集，且没有两个连续元素。

将被选元素之间的间隔压缩后，这些集合与一个

(17 - 2k)

-元素集合的

k

-子集一一对应，数量为

\binom{17 - 2k}{k}

。只有

k \le 5

时该数非零，所以总数为

\begin{gathered} \binom{15}{1} + \binom{13}{2} \\ {}+ \binom{11}{3} + \binom{9}{4} \\ {}+ \binom{7}{5} \\ = 15 + 78 + 165 + 126 + 21 \\ = 405 \end{gathered}\text{。}

因此，正确答案是 E。

By property

(2),

a valid

k

-element set is a

k

-subset of

\{k, k+1, \ldots, 15\}

with no two consecutive elements.

Collapsing the gaps between chosen elements, these correspond bijectively to

k

-subsets of a

(17 - 2k)

-element set, counted by

\binom{17 - 2k}{k}.

This is nonzero only for

k \le 5,

so the total is

\begin{gathered} \binom{15}{1} + \binom{13}{2} \\ {}+ \binom{11}{3} + \binom{9}{4} \\ {}+ \binom{7}{5} \\ = 15 + 78 + 165 + 126 + 21 \\ = 405. \end{gathered}

Thus, the correct answer is E.

2006 AMC 12A 第 25 题

答案：E

难度评级：2550

小提示：

大提示：

解答：

其他年份的第 25 题