Problem:
How many non-empty subsets S of {1,2,3,…,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
Solution:
For 1≤k≤15, the k-element sets with properties (1) and (2) are the k-element subsets of Uk​={k,k+1,…,15} that contain no two consecutive integers. If {a1​,a2​,…,ak​} is such a set, with its elements listed in increasing order, then {a1​+k−1,a2​+k−2,…,ak−1​+1,ak​} is a k-element subset of U2k−1​. Conversely, if {b1​,b2​,…,bk​} is a k-element subset of U2k−1​, with its elements listed in increasing order, then {b1​−k+1,b2​−k+2,…,bk−1​−1,bk​} is a set with properties (1) and (2). Thus for each k, the number of k-element sets with properties (1) and (2) is equal to the number of k-element subsets of the (17−2k)-element set U2k−1​. Because k≤17−2k only if k≤5, the total number of such sets is
k=1∑5​(k17−2k​)=(115​)+(213​)+(311​)+(49​)+(57​)=15+78+165+126+21=405​
The problems on this page are the property of the MAA's American Mathematics Competitions