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

解答：

由性质 $(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}$

因此，正确答案是 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 题