2006 AMC 12A Problem 25

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

A

k

-element valid set is a

k

-subset of

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

with no two consecutive

Such sets biject with

k

-subsets of a

(17 - 2k)

-element set, counted by

\binom{17 - 2k}{k}

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.

Problem 25 in other years