What is the number of non-empty subsets of list S possible such that

Question

List S = {1, 2, 4, 5, 7, 8}
What is the number of non-empty subsets of list S possible such that a subset does not contain consecutive numbers?

(A) 77
(B) 48
(C) 36
(D) 32
(E) 26

M37-51

Bunuel · Accepted Answer

Official Solution:

List  S = \{1, 2, 4, 5, 7, 8\} 
 
What is the number of non-empty subsets of list S possible such that a subset does not contain two or more consecutive numbers?

A.  77 
B.  48 
C.  32 
D.  27 
E.  26

There are three pairs of consecutive numbers in the list: (1, 2), (4, 5) and (7, 8). We need the subsets that do not contain any such pair. So, for each pair, we can have three options: {only the first number from this pair is in the subset, only the second number from this pair is in the subset, none of the numbers from this pair is in the subset}. For example, for (1, 2) pair we can have three options: {only 1 from this pair is in the subset, only 2 from this pair is in the subset, none of the numbers from this pair is in the subset}. Thus, the total number of subsets, that do not contain two or more consecutive numbers is  3*3*3=27  but this number will include an empty set (the case when none of the numbers from any pair is in the subset), so we should subtract that case. Final answer is therefore  27-1=26 .

Answer: E

chetan2u · Answer

Let us checks sets by the number of elements
(1)  Single element:  any one of the six elements in a set, so 6 sets
(2)  Two elements:  Any one from two of {1,2}, {4,5} and {7,8}. So 2*2*3C2=12
(3)  Three elements:  One from each of {1,2}, {4,5} and {7,8}. So 2*2*2=8
The moment we have 4 elements, at least one of {1,2}, {4,5} and {7,8} will have both the elements. Thus, there will surely be some consecutive numbers : {1,4,7, X}. X can be 2, 5 or 8, and each one of them will result in a pair of consecutive numbers.

Total = 6+12+8=26

E

Poojita · Answer

In the case of 3 elements in the set, why cant we think like this :
we need to fill 3 places so first can be filled in 6 ways, second in 4 ways( because we will exclude the number which is the consecutive number of the first selected number) and the third place in 2 ways( same reason) so no of ways we can have a set of 3 elements is 6*4*2=48?

nick1816 · Answer

We can divide the list S in 3 parts {1,2}, {4,5} and {7,8}

We have 3 options for each of the group. For example: Either 1 is present or 2 is present or neither of them is present in the subset.

Total possible subsets such that a subset does not contain consecutive numbers = 3*3*3=27

number of non-empty subsets = 27-1=26

Sharu2205 · Answer

Hi Poojita, the case of considering 6*4*2 is when the order of selection is important. Lets consider a combination (1,4,7), your case will give results as (1,4,7), (1,7,4), (4,7,1), (4,1,7), (7,1,4), (7,4,1) but these all are not different in this case because for us order of number is not important. so a single combination can be repeated 6 times. so the answer is (6*4*2)/6 = 8 combinations.

chetan2u · Answer

Hi

When you take 6*4*2, you will get arrangements where order matters, that is ABC will be different from BCA.

But here we are looking at selections or combinations. So divide 48 by the ways the 3 elements can be arranged within themselves, that is 3!

48/3!=48/6=8

Adarsh_24 · Answer

Another way almost similar to chetan2u.

1 digit => 6 numbers => 6

2 digits => 6C2 - 3 = 12
6C2-2 numbers can be selected from 6 in 6C2 ways
But, there are 3 chances where numbers are picked from adjacent groups 1-2,4-5,7-8
We subtract them

3 digits => 6C3 - 4C1*2C2*3 = 20-12=8
6C3-3 numbers can be selected from 6 in 6C3 ways
But, there are chances where numbers are picked from adjacent groups 1-2,4-5,7-8
Example:
1-2 both picked and 1 number from 4,5,7,8
Thats 2C2 and 4C1
This can happen for each pair. So multiplied by 3.
We need to subtract these.

At 4 digit, at least 1 consecutive pair will be present.

So ans = 6+12+8=26

bumpbot · Answer

Automated notice from GMAT Club BumpBot: 

A member just gave Kudos to this thread, showing it’s still useful. I’ve bumped it to the top so more people can benefit. Feel free to add your own questions or solutions.

 This post was generated automatically.

What is the number of non-empty subsets of list S possible such that

Prep Toolkit

Top 5 GMAT Debrief Videos

615 to 715 in 15 Days (Ria's Strategies)

More than Quant/Verbal Abilities: Speed vs. Accuracy

745 with Only Self-Prep and GMAT Club

From 555 to 765: 210-point Improvement

Perfect 805 Score Debrief by Julia

My Rewards

GMAT Problem Solving (PS) Questions

What is the number of non-empty subsets of list S possible such that

Prep Toolkit

615 to 715 in 15 Days (Ria's Strategies)

More than Quant/Verbal Abilities: Speed vs. Accuracy

745 with Only Self-Prep and GMAT Club

From 555 to 765: 210-point Improvement

Perfect 805 Score Debrief by Julia

My Rewards