M37-51

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 two or more consecutive numbers?

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

Bunuel · 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

punit2020 · Answer

set of 1 no = 6
set of 2 no = 12 (15 - 3; 15 total and 2 of consecutive numbers)
set of 3 no = 8 (20 - 12; total 20 and 8 containing consecutive numbers)
set of 4, 5 and 6 nos = not possible without consecutive numbers 
Answer = 6+12+8 = 26

umangshah · Answer

Is there a way of calculating the number of subsets for any given set of values?

Bunuel · Answer

If a set has n elements, then the number of subsets of that set is 2^n. This is because each element of the set has two options: it can be either included or not included in a subset. This count includes the empty set as well, which is a subset of every set. Therefore, the number of proper subsets (subsets with one or more elements) of the given set is 2^n - 1.

For example, consider the set {1, 2, 3}. The number of subsets of this set is 2^n = 2^3 = 8. These subsets include:

{} - an empty set
{1} - a subset containing only the element 1
{2} - a subset containing only the element 2
{3} - a subset containing only the element 3
{1, 2} - a subset containing the elements 1 and 2
{1, 3} - a subset containing the elements 1 and 3
{2, 3} - a subset containing the elements 2 and 3
{1, 2, 3} - the subset that contains all the elements, also known as the original set itself.

Hope it helps.

Gemmie · Answer

We have 3 subgroups of consecutive numbers: (1, 2); (3, 4); (5, 6)

To create the required subset (a subset does not contain two or more consecutive numbers)
=> From each group of these 3 group, we can choose to neither or either of 2 numbers but not both
=> 3 ways each

=> Total number of subsets:  3^3 = 27

However, the subset must not be empty => we have to exclude 1 arrangement where we do not choose any from all 3

=> Total number of non-empty subsets: 27 - 1 = 26

SudsMeister · Answer

How I tackled it:

Since subsets cannot contain 2 or more consecutive numbers so basically (1,2), (4,5), and (7,8) cannot be chosen together.

This further implies that subset cannot have more than 3 numbers as the moment we choose a 4th number, it becomes consecutive to one of the 3 numbers that was chosen previously.

For instance, we have already chosen 3 numbers, say (1, 4, 7). Now to add a 4th number to the set, we can either add 2, or 5, or 8. If we choose 2, it becomes consecutive with 1, if we choose 5, it becomes consecutive with 4, and if we choose 8, it becomes consecutive with 7. So, a subset with 4 numbers isn't possible. Using the same logic, subsets with 5 and 6 numbers also aren't possible.

So, only subsets with either 1, or 2, or 3 numbers are possible (null set isn't allowed as stated in the question).

Case 1:
Subset with 1 number = 6 numbers x 1 = 6 subsets.

Case 2:
Subset with 2 numbers without consecutive integers = 1st number can be chosen in 6 ways and 2nd number can be chosen in 4 ways (as choosing the 1st number eliminates that number as well as its consecutive partner number for further selection); but this contains ordering of elements, so we need to divide by 2! = 6 x 4 / 2! = 12 subsets.

OR

Subset with 2 numbers without consecutive integers = All possible choices of 2 number subsets - Subsets with only 2 consecutive integers = 6C2 - 3 x 2C2 = 15 - 3 = 12 subsets.

Case 3:
Subset with 3 numbers without consecutive integers = 1st number can be chosen in 6 ways, 2nd number in 4 ways (1st number's selection eliminates that number and its consecutive partner number for further selection), and 3rd number in 2 ways (2 numbers' selection eliminates those numbers and their consecutive partner numbers for further selection); but this contains ordering of elements, so we need to divide by 3! = 6 x 4 x 2 / 3! = 8 subsets.

OR

Subset with 3 numbers without consecutive integers = All possible choices of 3 number subsets - 3 number subsets with consecutive integers = 6C3 - Choosing 1 pair out of the 3 pairs of consecutive integers, and the 3rd number can be any number from the remaining 4 = 6C3 - 3C1 x 4 = 20 - 12 = 8 subsets.

Total subsets = Case 1 + Case 2 + Case 3 = 6 + 12 + 8 = 26 subsets.

Answer E.

For clarification, if the question didn't explicitly exclude the null set, we would have a Case 4 = no numbers chosen = 6C0 = 1 subset, and the total will become 27 subsets, making the answer D.

btsaami · Answer

Hi you seem to be very good with combinations, Could you please provide some insights as how to deal with this topic in a structured and long-lasting way?

SudsMeister · Answer

Honestly, practicing a variety of questions and deep diving into them - actually counting the cases in the first 10-20 difficult questions so that usage of the permutation and combination formula is something I can visualise in my brain easily - that helped me a lot.
I would suggest to start with OG, then use PS forum in GMAT Club, apply filter for Combinations + 555-655 Level Qs, do 30-40 of them and deep dive into each erroneous ones. The aim should be to be able to mentally imagine the scenarios in your head when you multiply different counts.

For instance: There are 10 students in a class and of them is Harry. In how many ways can you make a team of 3 students such that Harry is always a part of the team?
The most basic Q coming to the head would be should I use permutation or combination. You can solve it using both, but if you're able to mentally imagine that permutations / combinations would include which all possible scenarios, it would easier for you to reduce or increase the final count to get your answer.
Say, you go via permutations: Harry has taken the first spot, remaining 2 can be taken by 9 students X 8 students. The moment you use this formula / counting method - your brain should be able to map that (say the 3 students were Harry, A, and B) as per this method {Harry, A, B} and {Harry, B, A} are 2 separate scenarios as per your count even though for the purpose of forming a team both are the same. So, you must reduce your final count by 2! to get the right answer. 
If you choose combinations - Harry is already a part of the team, the other 2 can be chosen out of 9 in 9C2 ways. Now some may think we need to multiply the answer by 3! to get all possible options - and the choices might also have a trick answer containing 9C2 x 3! as an option - but one must have enough clarity to ask themselves - are {Harry, A, B}, {Harry, B, A}, {A, Harry, B}, {A, B, Harry}, {B, Harry, A}, and {B, A, Harry} all separate teams are all these the same team?

Once this imaging can be done mentally or very swiftly on pen and paper - then slowly and steadily your brain will automatically retain that which counting methods would include or preclude which scenarios.

Later change the filter in PS forum, move to 655-705 level Qs for Combinations and spend some time fleshing out all scenarios in the erroneous questions.
You should gradually see your understanding and grasp of the topic improve.

M37-51

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