AMC 12A 2006 Problem 25

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.

Answer Choices
A. 277
B. 311
C. 376
D. 377
E. 405