We say that a set of integers is sparse if any two 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.)

MathProblemSolver101 Nov 25, 2020

#1**0 **

12 C 2 = 66 ways of subtracting one element from another. If you do that, this is what you will get:

(1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 8, 9, 9, 9, 10, 10, 11)>Total = 66

Just count all the elements 3 and above to get your "sparse subsets".

Guest Nov 26, 2020