+0

# Counting Problem

0
156
4

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.)

Aug 17, 2022

#1
+1263
+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}$$.

Aug 17, 2022
#2
0

Thank you so much!

Aug 17, 2022
#3
+1263
+2

jimkey17  Aug 17, 2022
#4
+2
0

interesting information

Aug 18, 2022
edited by lavivavola  Aug 18, 2022
edited by lavivavola  Aug 18, 2022
edited by lavivavola  Aug 18, 2022