Lesson: GMAT Counting Strategies - Part II

Comment on GMAT Counting Strategies - Part II

Hi Brent,

How we should go about with problems that involves identical objects and the outcome of one stages does not differ from the outcome of other stage i.e. it is a MISSISSIPI Rule + Combination problem?
gmat-admin's picture

Hmmm, I'm trying to think of a question that meets these conditions. The problem is that the MISSISSIPPI rule implies that the order of the letters matters, whereas we typically use combinations when the order doesn't matter.

Do you have an example question in mind?

http://gmatclub.com/forum/in-how-many-different-ways-can-3-identical-green-shirts-and-105384.html

This is question that involves identical objects and where order does not matter. Generally the solutions employ MISSISSIPI Rule. Since the order does not matter in the question, there is one solution that solves it with Combination technique (however it is appears quite tricky). Hence, I am unsure how to go about in such cases. And how these both techniques are related to each other.
gmat-admin's picture

That question (http://gmatclub.com/forum/in-how-many-different-ways-can-3-identical-gre...) is unique in that we can look at it in two different ways.

We can think of it as ordering the letters RRRGGG such that child #1 gets the color indicated by the 1st letter, child #2 gets the color indicated by the 2nd letter, etc. In this approach, we can apply the MISSISSIPPI rule.

Alternatively, we can think of it as simply CHOOSING which 3 children receive a red shirt (and the remaining 3 children receive the green shirt). In this approach, you can use combinations.

This really shouldn't pose a problem for you. Instead, it's a bit of a gift, since we can use EITHER method to solve it. That's a good thing :-)

Hi Brent, first of all, thanks a lot again for these brilliant videos, I find them very helpful!

So, after reading your post, I understand your solution/ explanation here: http://www.beatthegmat.com/if-a-committee-of-3-people-is-to-be-selected-t292338.html

But I do wonder where I'm wrong with this line of reasoning:
- After Stage One, we have 3 married couples (6 people) to choose from.
- I then proceeded to calculate the rest by using the FCP:

Since we want to choose 3 people, and the 3 selections are equally restrictive (I think? the only restriction being "not married to another person on the committee") we can choose them in the following order: ___1st___ , ___2nd___ , ___3rd___

- There are 6 ways to choose the first person, and since his/her spouse cannot be chosen after making the first selection, there will be 4 more people to choose from for the second position, and applying the same logic, there will be 2 ways left to select the third person, so using the FCP I calculated 6x4x2..

Which, of course, yielded a wrong answer, but I can't seem to see the flaw in my line of reasoning. Maybe you can help shed some light on this issue?

Many thanks,
Kai
gmat-admin's picture

The only problem with your approach is that it treats the outcome of stage 1 as different from the outcome of stage 2.

Let's represent the 6 people as A, a, B, b, C, c (where A and a are a couple, as are B and b etc)

In your approach, selecting A then b then C is considered different from selecting b then C then A, when they both yield the same committee.

In fact, your approach takes each arrangement and counts each of them 6 times. For example, in your approach, the following committees are considered different: bCA, bAC, AbC, ACb, CAb, CbA

NOTE: there are 3! ways to arrange A, b and C.

So, to account for all of this duplication, we must take your result of 6x4x2 and divide it by 6 (aka 3!). if you do this, then you will get the correct answer.

Dear Brent,

I solved the "In a meeting of 3 representatives from each of 6 different companies, each person shook hands with every person not from his or her own company. If the representatives did not shake hands with people from their own company, how many handshakes took place?" Question using the subtracting the unwanted results rule.

Total number of Handshakes possible = 18C2 = 153
Total number of same company hanshakes = 6 companies x 3C2
= 6 x 3 = 18
Therefore no of other company handshakes = 153 - 18 = 135
gmat-admin's picture

Question link: https://gmatclub.com/forum/in-a-meeting-of-3-representatives-from-each-o...

That's a perfectly valid approach, aashaybaindur - well done!

Brent,

Could you explain me the exercises #169 & #207 from OG17 using the restriction rule?

Thanks
Pedro
gmat-admin's picture

Hi Pedro,

Those questions don't lend themselves to using the restriction rule (especially question #207).

Cheers,
Brent

Hi Brent,
This question is in the practice questions given below.But i am not able to see any expert reply on this.
Can you please give me solution of this question.

A researcher plans to identify each participant in a certain medical experiment with a code consisting of either a single letter or a pair of distinct letters written in alphabetical order. What is the least number of letters that can be used if there are 12 participants, and each participant is to receive a different code?

A. 4
B. 5
C. 6
D. 7
E. 8
gmat-admin's picture

Thanks

Hi Brent, I have a doubt? In this question: https://gmatclub.com/forum/jack-is-making-a-list-of-his-5-favorite-cities-he-will-choose-3-citie-239856.html you solved the problem this way: 5C3 * 3C2 * 5!, I understood the first two stages but not the last one. If I multiply per 5! I would not take the risk of set a city which was already set in the first two stages?
gmat-admin's picture

Question link: https://gmatclub.com/forum/jack-is-making-a-list-of-his-5-favorite-citie...

In stages 1 and 2, I am selecting my 5 cities (3 US cities and 2 European cities). So, let's say the 5 cities are: Seattle, Chicago, Miami, Paris and Madrid.

However, at this point, all we have done is select the 5 cities; we have not yet RANKED them from 1st to 5th (as the question directs us to do).

So, for example, some possible rankings are:
- 1st-Seattle, 2nd-Paris, 3rd-Madrid, 4th-Chicago, 5th-Miami
- 1st-Chicago, 2nd-Miami, 3rd-Madrid, 4th-Seattle, 5th-Paris
- 1st-Miami, 2nd-Chicago, 3rd-Paris, 4th-Seattle, 5th-Madrid
etc

So, we must still count the various ways we can rank the cities (5! ways). We handle this task in stage 3.

Does that help?

Cheers,
Brent

ari.banerjee's picture

Hi Bret,

Can you please explain the solution to the following problem you posted on GMATCLUB? I dont understand the solutions that were provided by other experts.

Several teams are competing in a basketball tournament, and each team plays every other team once. Each game has exactly 1 winner and 1 loser (no ties). If 4 teams lost exactly 5 games, 5 teams won exactly 3 games, and each of the remaining teams won all of its games, what is the total number of games played during the tournament?

A) 36
B) 45
C) 55
D) 66
E) 78

Can we see a problem of this magnitude on the GMAT? This seemed really hard. I would've guessed and moved on and not wasted my time on it. But I am def curious to know if there is an easier solution to this.
Thank you,

Ari
gmat-admin's picture

Question link: https://gmatclub.com/forum/several-teams-are-competing-in-a-basketball-t...

I was quite proud of that question UNTIL someone pointed out a serious flaw: If each team plays every other team, then it's impossible for 2 or more teams to win EVERY game, since those teams would have played each other, which means one of the teams had to lose.

That said, if we ignore the flaw, it's a very time-consuming question, AND it's a 750+ level question. So, guessing and moving on would be a good idea.

Here's the solution I posted on a different forum BEFORE someone pointed out the flaw in my question.

https://greprepclub.com/forum/tricky-there-are-n-teams-playing-in-a-bask...

ari.banerjee's picture

Hi Brent,

Could you please show a humanly way of solving this Qs? I dont understand the explanation on Gmatclub at all.

Its an OG question to top it all so I am really worried that I dont get the concept.

A researcher plans to identify each participant in a certain medical experiment with a code consisting of either a single letter or a pair of distinct letters written in alphabetical order. What is the least number of letters that can be used if there are 12 participants, and each participant is to receive a different code?

https://gmatclub.com/forum/a-researcher-plans-to-identify-each-participant-in-a-certain-134584.html

Many thanks in advance!

Hi Brent :) I don't understand exercise 201 in the gmat official guide 2019. Can you give me your solution?
gmat-admin's picture

Hi Brent ,

I needed some help with 2 questions :

1. https://gmatclub.com/forum/m06-183708.html : Why did we divide it by 4! here ? Shouldnt it be multiplied instead ?

2. https://gmatclub.com/forum/m26-184458.html : Like the 3 sixes can assume any positions within the 5 numbers , Cant the 2 numbers interchange the position between themselves , shouldn’t we multiply it by 2 ? like 66465 and 66564 ?

Thankyou !
gmat-admin's picture

1. https://gmatclub.com/forum/m06-183708.html
I'm not a big fan of this question, because it's unclear whether the 4 teams are considered the same or different.
For example, is Team 1 = A&B, Team 2 = C&D, Team 3 = E&F, Team 4 = G&H different from Team 2 = A&B, Team 1 = C&D, Team 3 = E&F, Team 4 = G&H?
Since the official answer is B, we know that the INTENT of the question is to consider the two above configurations as equal.

In Bunuel's solution, he first treated the configurations as different, which means he counted many configurations more than once.
In fact, we can take the 4 different pairs and arrange them in 4! different ways (24 ways).
This means the first part of Bunuel's solution counted each configuration 24 times.
To account for this, he divided that value by 4! (aka 24)

2. https://gmatclub.com/forum/m26-184458.html
I'd have to see your full solution to determine whether you need to multiply your answer by 2.
In the meantime, here's my full solution: https://gmatclub.com/forum/m26-184458-20.html#p2301977

Cheers,
Brent

https://gmatclub.com/forum/if-a-committee-of-3-people-is-to-be-selected-from-among-88772-20.html#p1729049

In this question. I am looking to calc it by Total-no. of ways to break it
Total ways is 10C3 = 120 - No. of ways committee includes 2 members who are couple

I then looked to use FCP _ _ _ = 10*1*8 = 80

120-80 = 40. Which is wrong. Please advise?
gmat-admin's picture

Question link: https://gmatclub.com/forum/if-a-committee-of-3-people-is-to-be-selected-...

The problem with your solution is that, for the number of ways to BREAK the restriction, you're counting each outcome TWICE.

You are saying there's 10 ways to select any one person.
Then, in order to break the restriction, you next choose that person's partner, and this can be done in 1 way.

So, for example, let's say A and B are a couple,
In your approach, we might choose A first and then choose B second.
Or, we might choose B first and then choose A second.
Your solution treats these two outcomes as DIFFERENT, when they are clearly the same.

Rather than choose 2 people from the same couple, just choose 1 COUPLE.

We can choose 1 COUPLE in 5 ways.
We can then choose 1 of the 8 remaining people in 8 ways.
So, the total number of ways to break the restriction = (5)(8) = 40

Correct answer = 120 - 40 = 80

Does that help?

Cheers,
Brent

Hi Brent,
https://gmatclub.com/forum/what-is-the-number-of-the-shortest-routes-from-x-to-y-through-z-233292.html

Instead of stopping at Z to calculate the first 4 steps, I calculated from the start till the end, wherein I got 3Rs 3Us (both ways by starting from the right side). So I calculated 6!/3!3! from which I got 20 instead of 12. Can you please help me understand where am I wrong here?

Thank you!
gmat-admin's picture

Question link: https://gmatclub.com/forum/what-is-the-number-of-the-shortest-routes-fro...

That's a good idea. The only problem is that not all arrangements of 3 R's and 3 U's will pass through point Z.
For example, RRRUUU gets to point Y, BUT the path does not pass through point Z.

Likewise, RRURUU does not pass through point Z.
And URUURR does not pass through point Z.
etc

Cheers,
Brent

Hi Brent, Q DS06659 of OG 2019 -
"S is a set of points in the plane. How many distinct triangles can be drawn that have 3 of the points in S as vertices
(1) there number of distinct points in S is 5.
(2) no three of the points in S are collinear."

Here the official answer is C, but shouldn't it be E because one of the factors of making a triangle is that sum of any 2 sides is greater than the 3rd side. So if there are any 3 points with distance 1, 2 and 3, in that case a triangle cannot be made. This way possible answers could be 9 (10-1).
gmat-admin's picture

That's a good idea, Kashaf, but there aren't 3 such points so that the three lengths are 1, 2 and 3 (if try to find three points that meet that condition, you'll find that it's impossible to do so).

As long as we have three non-collinear points, we can always connect them to create a triangle.

Cheers, Brent

hello sir!
greeting of the day!
needed your help with this question and is this type of question expected on the test day?

https://gmatclub.com/forum/each-in-the-mileage-table-above-represents-an-entry-indica-95162.html

thank you
tanya
gmat-admin's picture

Here's my full solution: https://gmatclub.com/forum/each-in-the-mileage-table-above-represents-an...

This is an official (retired) GMAT question, so it's well within the scope of the test.

Cheers,
Brent

hello sir,
greetings of the day!

Can you provide a better solution for this question-
https://gmatclub.com/forum/a-researcher-plans-to-identify-each-participant-in-a-certain-medical-134584.html

thank you,
Tanya
gmat-admin's picture

https://gmatclub.com/forum/a-certain-team-consists-of-4-professors-and-6-teaching-assistants-how-219096.html

The way I tried solving this is.

__ x __ x __

--> total ways = 4 x 9 x 8 = at least 1 prof x all remaining x all remaining

Then 4 x 9 x 8 / 3! ( to remove the effect of the placement)

= 48


Could you tell me why this approach is wrong? Hope you understand what I'm trying to say.

gmat-admin's picture

Question link: https://gmatclub.com/forum/a-certain-team-consists-of-4-professors-and-6...

The problem is that, by dividing by 3!, you're assuming that your solution counts each unique outcome SIX times.
This, however, is not true.

Here's what I mean.
Let A, B, C and D represent the four professors.
And let e, f, g, h, i, j represent the six teaching assistants

So, for example, one outcome is A, f, C
Another outcome is A, C, f
Another outcome is C, f, A
Another outcome is C, A, f
Notice that all FOUR outcomes represent the SAME outcome.
Also notice that there are no other possible outcomes involving A, C and f, since your solution explicitly states that the first selection must be a professor.

IMPORTANT: Given this, you might conclude that we need only divide your solution by 4 to get the correct answer.
Unfortunately, this won't work either, since some identical outcomes are counted FOUR times, some identical outcomes are counted TWO times, and some identical outcomes are counted SIX times.

For example, one outcome is A, i, h
Another outcome is A, i, h
Notice that the TWO outcomes represent the SAME outcome.
Also notice that there are no other possible outcomes involving A, B and h, since your solution explicitly states that the first selection must be a professor.

One more example:
One outcome is A, B, C
Another outcome is A, C, B
Another outcome is B, A, C
Another outcome is B, C, A
Another outcome is C, A, B
Another outcome is C, B, A
In case there are SIX outcomes representing the same outcome.

I hope that helps.

Cheers, Brent

Hi Brent,

Thank you for the detailed reply, but I'm still confused.

My learning so far has been-
1. Use FCP
2. if positions don't matter, then you divide it by number of options factorial to remove the effect of the placements

So how do you know when to use this method or not? because on the earlier questions (which also had restrictions) this method worked.

Hope I could articulate my question well.
gmat-admin's picture

I've seen other resources/instructors advocate for step number 2, but it isn't part of my general strategy.
Here's my general strategy: https://www.gmatprepnow.com/module/gmat-counting/video/791

That said, you can certainly use approach #2. However, before applying it, you must be certain that each unique outcome has been counted the same number of times.
In the above case, some outcomes are counted twice, other outcomes are counted four times, and other outcomes are counted six times.

Hi Brent,

The 95% hard questions are just unsolvable. They are creating more confusion


https://gmatclub.com/forum/an-office-comprised-of-eight-employees-is-planning-to-have-a-foosball-246043.html


> Will we not take 4C2 in the second part. Cause Im multiplying the answer by 6.
Is there a different rule we need to remember for pairs?

gmat-admin's picture

Question link: https://gmatclub.com/forum/an-office-comprised-of-eight-employees-is-pla...

I totally agree; it's a crazy hard question (23% success rate!)

Good question about using 4C2 for stage 2 of my solution.
To see why this won't work, consider this question:

How many ways can Joe choose 2 of his 4 friends to join him on a fishing trip?
In this case, the answer is 4C2
So for example, if the 4 friends are A, B, C and D, then the 6 possible selections are:
AB
AC
AD
BC
BD
CD
Notice that, if Joe selects A & B, then B & C don't get to go on the fishing trip.
Likewise, if Joe selects B & D, then A & C don't get to go on the fishing trip.

This is a much different situation then what occurs in step 2 in my solution.
STEP 2: Divide the 4 selected employees into 2 teams
In this case, it isn't a matter of choosing two people to be on the team and telling the other two people to go home. In this case, the two selected people are on a team, have the two people not selected are also on a team.
Here's what I mean:
Let the four employees be A, B, C and D.
If we select A & B to be on one team, then that also implies that C & D are all the other team.
So, selecting A & B in stage 2 is the same as selecting C & D in stage 2, since both result in the same composition of teams.
This means there are only three unique outcomes:
- Select A & B to be on a team (which implies C & D are on the other team)
- Select A & C to be on a team (which implies B & D are on the other team)
- Select A & D to be on a team (which implies B & C are on the other team)

Does that help?

Thanks for the detailed reply. This makes a lot of sense now.

Learning - If objects are being paired into teams then I will manually count the options.

Hi Brent.
Good Evening.
Regarding Question - https://gmatclub.com/forum/an-integer-is-said-to-be-diverse-if-no-two-of-its-digits-are-the-sam-204909.html,
I thought to solve in in 2 ways but solution 1 didn't work, can you please explain why?:
Solution 1:
Breaking down the solution in stages:
Stage 1: Choose a digit in Unit place
Stage 2: Choose a digit in Tenth place

Stage 1 can be completed in 10 ways as there are 10 digits to fit in (0,1,...,9).
Stage 2 can be completed in 8 ways as we have already selected 1 digit for unit place among (1,2,...,9).
If we apply FCP, 8x10 becomes 80.
Unfortunately, this is not an option.

Solution 2:
Breaking down the solution in stages:
Stage 1: Choose a digit in Tenth place
Stage 2: Choose a digit in Unit place

Stage 1 can be completed in 9 ways as there are 9 digits to fit in (1,2,...,9).
Stage 2 can be completed in 9 ways as we have already selected 1 digit for Tenth place among (0,1,2,...,9).
If we apply FCP, 9x9 becomes 81.
How is solution 1 wrong?
gmat-admin's picture

There's a problem with Stage 2 of Solution 1, where you write:
"Stage 2 can be completed in 8 ways as we have already selected 1 digit for unit place among (1,2,...,9)."

We know that the tens digit can't equal 0. So, what happens if we choose a 0 in Stage 1 (when choosing the units digit)?
If we choose 0 for the units digit, then we have 9 options for the tens digit (1,2,3,4,5,6,7,8 or 9)
If we choose 1 for the units digit, then we have 8 options for the tens digit (2,3,4,5,6,7,8 or 9)

This is the reason we say that, when using the Fundamental Counting Principle (FCP), always start with the most restrictive stage.
In this case, choosing the tens digit is most restrictive, since it can't equal 0.

Hi Brent,

Can you solve this question in another approach - that is without listing the numbers?

https://gmatclub.com/forum/of-the-three-digit-integers-greater-than-700-how-many-have-two-digits-135188.html

Hi Brent Another query:

I just attempted to solve two questions that were similar in nature, the questions were:

Q1. https://gmatclub.com/forum/how-many-ways-can-the-five-digits-3-3-4-5-6-be-arranged-into-a-5-d-261844.html

Q2. https://gmatclub.com/forum/in-how-many-ways-can-the-letters-of-the-word-manifold-be-arr-167127.html

In both questions, I understood Stage 1. However, why is stage 2 solved in two different methods in both the questions?

In Q1, stage 2 is solved by using combinations, however, in the second question, it's solved using the Fundamental Counting Principle.

In both questions, I believe the order of the sequence does not matter, so what am I missing here?
gmat-admin's picture

My solution to Q1: https://gmatclub.com/forum/how-many-ways-can-the-five-digits-3-3-4-5-6-b...
My solution to Q2: https://gmatclub.com/forum/in-how-many-ways-can-the-letters-of-the-word-...

As you can, see both of my solutions are similar. I first arranged the letters that had no restrictions placed on them, then I added spaces for the remaining letters, and then I counted the number of ways to place the remaining letters in the spaces provided.

Here's where the difference occurs:
In question 1, I had to place two IDENTICAL 3's in the spaces.
In question 2, I had to place three DIFFERENT vowels (A, I and O) in the spaces.

So, for example, when choosing two spaces to place the two 3's (in Q1), placing one 3 in the first space and one 3 in the last place is the SAME as placing one 3 in the last space and one 3 in the first place. So, in this case, the order in which we place the two 3's does NOT matter.

Conversely, when choosing two spaces to place the A and I (in Q2), placing the A in the first space and the I in the last place is DIFFERENT from placing the A in the last space and the I in the first place. So, in this case, the order in which we place the A and I DOES matter.

Does that help?

Hi Brent,

Yes, got that, thank you for explaining. So either way, I can use the Fundamental counting principle for Stage 2 for both questions and the answer would still be the same.
gmat-admin's picture

That's correct. You just need to be on the lookout for any duplication, and then account for that.

Brent, I have no clue how you filled out this matrix with exception of the bottom right lol.

https://gmatclub.com/forum/in-how-many-different-ways-can-6-identical-belts-and-5-identical-hats-307440.html
gmat-admin's picture

Good point! I kind of glossed over that part.
I went back and added some extra information to my solution here: https://gmatclub.com/forum/in-how-many-different-ways-can-6-identical-be...

Pages

Practice Wisely

While solving GMAT quant questions, always remember that your one goal is to identify the correct answer as efficiently as possible, and not to please your former math teachers. 

Change Playback Speed

You have the option of watching the videos at various speeds (25% faster, 50% faster, etc). To change the playback speed, click the settings icon on the right side of the video status bar.

Have a question about this video?

Post your question in the Comment section below, and a GMAT expert will answer it as fast as humanly possible.

Free “Question of the Day” emails!