We say that a set of integers is sparse if any two distinct elements in the set differ by at least **3**. Find the number of sparse subsets of **{1, 2, 3, ... , 12}**. (Note that the empty set is also sparse.)

Guest Aug 17, 2022

#1**+2 **

The sparse subsets of {1} are {} and {1}, so there are 2 subsets of {1}.

The sparse subsets of {1,2} are {}, {1}, and {2}, so there are 3 subsets of {1,2}.

The sparse subsets of {1,2,3} are {}, {1}, {2}, and {3}, so there are 4 subsets of {1,2,3}.

The sparse subsets of {1,2,3,4} are {}, {1}, {2}, {3}, {4}, and {1,4} so there are 6 subsets of {1,2,3,4}.

The sparse subsets of {1,2,3,4,5} are {}, {1}, {2}, {3}, {4}, {5}, {1,4}, {1,5} and {2,5} so there are 9 subsets of {1,2,3,4,5}.

We found a pattern! The number of sparse subsets of {1,2,3, ... ,n} is the number of subsets of {1,2,3, ... ,n-1}+{1,2,3, ... ,n-3}. So the number of subsets of {1,2,3, ... ,12} is \(\boxed{\text129}\).

jimkey17 Aug 17, 2022