+0  
 
0
57
4
avatar

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
avatar+1262 
+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
avatar
0

Thank you so much!

 Aug 17, 2022
 #3
avatar+1262 
+2

Your welcome.

jimkey17  Aug 17, 2022
 #4
avatar+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

24 Online Users