+874 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.)
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".
