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