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$

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 $\binom{15}{1} + \binom{13}{2} + \binom{11}{3} + \binom{9}{4} + \binom{7}{5} = 15 + 78 + 165 + 126 + 21 = 405.$

Thus, the correct answer is E.

2006 AMC 12A Problem 25

Solution:

Problem 25 in Other Years