Question

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$

Answer: E

Concepts:subsets bijection combinations

Difficulty rating: 2550

Solution:

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 Problem 25

Answer: E

Difficulty rating: 2550

Solution:

Problem 25 in Other Years