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, 13, 14 (Note that the empty set is also sparse.)

Guest May 15, 2021

#2**+1 **

I do not know what the answer is, but, in listing some sets, I get more than 56 sets when counting only those that include the number 1.

geno3141 May 15, 2021

#3**+2 **

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, 13, 14 (Note that the empty set is also sparse.)

I get 51 that are NOT sparse

The number of subsets altogther is

1+14+14C2+14C3+14C4+14C5+14C6+14C7+14C8+14C9+14C10+14C11+14C12+14C13+14C14

=2+28+2(14C2+14C3+14C4+14C5+14C6)+14C7

=30+2(14C2+14C3+14C4+14C5+14C6)+14C7

=30+2(91+364+1001+2002+3003)+3432

=3462+2(6461)

=16384

So the number of subsets that are sparse is 16384-51 = 16333

Melody May 16, 2021