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