Problem:
Call a set of integers spacy if it contains no more than one out of any three consecutive integers. How many subsets of {1,2,3,…,12}, including the empty set, are spacy?
Answer Choices:
A. 121
B. 123
C. 125
D. 127
E. 129
Solution:
For each positive integer n, let Sn​={k:1≤k≤n}, and let cn​ be the number of spacy subsets of Sn​. Then c1​=2,c2​=3, and c3​=4. For n≥4, the spacy subsets of Sn​ can be partitioned into two types: those that contain n and those that do not. Those that do not contain n are precisely the spacy subsets of Sn−1​. Those that contain n do not contain either n−1 or n−2 and are therefore in one-to-one correspondence with the spacy subsets of Sn−3​. It follows that cn​=cn−3​+cn−1​. Thus the first twelve terms in the sequence (cn​) are 2,3,4,6,9,13,19,28,41,60,88,129, and there are c12​=129​ spacy subsets of S12​.
OR
Note that each spacy subset of S12​ contains at most 4 elements. For each such subset a1​,a2​,…,ak​, let b1​=a1​−1,bj​=aj​−aj−1​−3 for 2≤j≤k, and bk+1​=12−ak​. Then bj​≥0 for 1≤j≤k+1, and
b1​+b2​+⋯+bk+1​=12−1−3(k−1)=14−3k
The number of solutions for (b1​,b2​,…,bk+1​) is (k14−2k​) for 0≤k≤4, so the number of spacy subsets of S12​ is
(014​)+(112​)+(210​)+(38​)+(46​)=1+12+45+56+15=129​
The problems on this page are the property of the MAA's American Mathematics Competitions