+0  
 
0
268
3
avatar

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

 May 15, 2021
 #1
avatar
0

There are 56 such sets.

 May 15, 2021
 #2
avatar+22169 
+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.

 May 15, 2021
 #3
avatar+114533 
+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

 May 16, 2021

11 Online Users

avatar