Combinatorics

BREAKING: Target Test Prep releases Brand New 2026 On Demand GMAT prep course

Redeem

This topic has expert replies

Post new topic Post Reply

Previous Topic Next Topic

adthedaddy: Master | Next Rank: 500 Posts; Posts: 167; Joined: Fri Mar 09, 2012 8:35 pm; Thanked: 39 times; Followed by:3 members

Combinatorics

by adthedaddy » Tue Oct 09, 2012 9:31 am

What is the total number of ways of selecting twenty balls from an infinite number of blue, green and
yellow balls?

1. 3^20
2. 20^3
3. 231
4. 1771

OA -> 231

"Your time is limited, so don't waste it living someone else's life. Don't be trapped by dogma - which is living with the results of other people's thinking. Don't let the noise of others' opinions drown out your own inner voice. And most important, have the courage to follow your heart and intuition. They somehow already know what you truly want to become. Everything else is secondary" - Steve Jobs

Quote

Source: Beat The GMAT — Problem Solving | Tue Oct 09, 2012 9:31 am

GMAT/MBA Expert

Whitney Garner: GMAT Instructor; Posts: 273; Joined: Tue Sep 21, 2010 5:37 am; Location: Durham, NC; Thanked: 154 times; Followed by:74 members; GMAT Score:770

by Whitney Garner » Tue Oct 09, 2012 10:35 am

adthedaddy wrote:What is the total number of ways of selecting twenty balls from an infinite number of blue, green and yellow balls?

1. 3^20
2. 20^3
3. 231
4. 1771

OA -> 231

Hi adthedaddy!

First I want to note that this is a fairly irregular question for the GMAT as it requires the knowledge of combinations WITH repetition, and that is fairly rare. But let's give it a shot together.

First let's talk about the formula for combinations w/ repetition:

DEFINITION: The number of ways to sample k elements (this is how many I am picking) from a set of n elements (these are the # of types I'm picking from) allowing for duplicates (i.e., with replacement) but disregarding different orderings (i.e. {rgb} & {grb} are NOT different choices just because we rearranged the order) is given by the formula

**I have just presented the various ways people might be used to writing combination formula, these are all actually equivalent.

Okay, if you have any questions about how that final factorial is derived, remember that the denominator of a combination must SUM to the value in the numerator, so k + (n-1) has to add to give us (n+k-1) and it does.

Now let's get started. We want to select 20 balls (that would mean our k=20), from a choice of 3 different colors (n=3) and we can have as many of each color as we want (so we have repetition). Now we just plug in...

So the answer is [spoiler](3) 231.[/spoiler].

Be careful, a tempting answer is 3^20, because we have 20 decisions to make and each decision has 3 choices (red, green, blue), BUT this does NOT disregard different orderings. This would be the PERMUTATION of ways we could choose (i.e. we assume that it matters that I picked something first, or 3rd, etc).

Hope this helps!

Whit

Whitney Garner
GMAT/GRE/EA Instructor & Anxiety/Accommodations Coach
www.whitneygarner.com

Contributor to Beat The GMAT!

Math is a lot like love - a simple idea that can easily get complicated

Quote

adthedaddy: Master | Next Rank: 500 Posts; Posts: 167; Joined: Fri Mar 09, 2012 8:35 pm; Thanked: 39 times; Followed by:3 members

by adthedaddy » Tue Oct 09, 2012 10:48 am

Hi Whit,
First of all thankyou for the solution.

But I am not able to understand (a) how did you come to know that this question requires knowledge of combinations with repetition and (b) is there any other alternate way to solve this apart from the following method ?

Quote

GMAT/MBA Expert

Whitney Garner: GMAT Instructor; Posts: 273; Joined: Tue Sep 21, 2010 5:37 am; Location: Durham, NC; Thanked: 154 times; Followed by:74 members; GMAT Score:770

by Whitney Garner » Tue Oct 09, 2012 11:05 am

adthedaddy wrote:Hi Whit,
First of all thankyou for the solution.

But I am not able to understand (a) how did you come to know that this question requires knowledge of combinations with repetition and (b) is there any other alternate way to solve this apart from the following method ?

Hi adthedaddy!

Let me start with the easier question first (b). Unfortunately there is no other way to solve this problem other than to recognize this as a combinations WITH repetition problem. As you might suspect, without this, there is no way to figure out that we need a 22! in the numerator. BUT, there is a great explanation of another way to think about what is going on here (https://www.mathsisfun.com/combinatorics ... tions.html - scroll all the way to the bottom for an awesome discussion of Combinations with Repetition).

Now to the slightly more unhappy of your 2 questions, (c). The only way to know this is to have seen them before! But now you have so AWESOME! Okay, so what gives us combinations with repetition. It is when we can choose from a certain type repeatedly to get our outcome. So here, we can choose repeatedly from red balls, or repeatedly from blue balls, or repeatedly from green balls. There is no end to the number of each we can pick and it isn't the case that once we pick one, we can't choose it again (that is the "infinite" part of this problem).

Let me know if this chips away at the confusion, and if not, I'll just try harder!

Whit

Whitney Garner
GMAT/GRE/EA Instructor & Anxiety/Accommodations Coach
www.whitneygarner.com

Contributor to Beat The GMAT!

Math is a lot like love - a simple idea that can easily get complicated

Quote

GMATGuruNY: GMAT Instructor; Posts: 15539; Joined: Tue May 25, 2010 12:04 pm; Location: New York, NY; Thanked: 13060 times; Followed by:1906 members; GMAT Score:790

by GMATGuruNY » Tue Oct 09, 2012 1:28 pm

adthedaddy wrote:What is the total number of ways of selecting twenty balls from an infinite number of blue, green and
yellow balls?

1. 3^20
2. 20^3
3. 231
4. 1771

The problem above is no different from the following:

On a table are 3 boxes: a blue box, a green box and a yellow box. How many ways can 20 identical balls be distributed among the 3 boxes?

Placing 5 balls in the blue box, 5 balls in the green box, and 10 balls in the yellow box = selecting 5 blue balls, 5 green balls, and 10 yellow balls in the problem above.

To solve, we can use the SEPARATOR method.

The 20 identical balls are to be separated into -- at most -- 3 groupings.
Thus, we need 20 balls and two separators:
OOOOOOOO|OOOOOOO|OOOOO

Each arrangement of the elements above represents one way to distribute the 20 balls among three boxes B, Y and G:
OOOOOOOO|OOOOOOO|OOOOO = B gets 8 balls, Y gets 7 balls, G gets 5 balls.
OO||OOOOOOOOOOOOOOOOOO = B gets 2 balls, Y gets 0 balls, G gets 18 balls.
OOOOOOOOOOOOOOOOOOOO|| = B gets all 20 balls.
And so on.

To count all of the possible distributions, we simply need to count the number of ways to arrange the 22 elements above (the 20 identical balls and the two identical separators).
The number of ways to arrange 22 elements = 22!.
But when an arrangement includes identical elements, we must divide by the number of ways to arrange the identical elements.
The reason:
When the identical elements swap positions, the arrangement doesn't change, reducing the total number of unique arrangements.
Here, we must divide by 20! (the number of ways to arrange the 20 identical balls) and 2! (the number of ways to arrange the two identical separators):
22!/20!2!= 231.

The correct answer is C.

Private tutor exclusively for the GMAT and GRE, with over 20 years of experience.
Followed here and elsewhere by over 1900 test-takers.
I have worked with students based in the US, Australia, Taiwan, China, Tajikistan, Kuwait, Saudi Arabia -- a long list of countries.
My students have been admitted to HBS, CBS, Tuck, Yale, Stern, Fuqua -- a long list of top programs.

As a tutor, I don't simply teach you how I would approach problems.
I unlock the best way for YOU to solve problems.

For more information, please email me (Mitch Hunt) at [email protected].
Student Review #1
Student Review #2
Student Review #3