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

Redeem

Challenging non-GMAT combinatorics question

This topic has expert replies
Post new topic Post Reply
Previous Topic Next Topic
Master | Next Rank: 500 Posts
Posts: 199
Joined: Sat Apr 26, 2014 10:53 am
Thanked: 16 times
Followed by:4 members
GMAT Score:780

Challenging non-GMAT combinatorics question

by 800_or_bust » Sun Jun 12, 2016 5:58 am
Can anybody help me with this? It's probably more difficult than anything that would appear on the GMAT. I came up with this question in an attempt to challenge myself, but I'm having a hard time conceptualizing the answer. Any insight is appreciated?

In how many different ways can six unique coins - a penny, a nickel, a dime, a quarter, a half dollar, and a silver dollar - be distributed among three people, such that each coin is distributed and each person receives at least one coin?
800 or bust!
Top
Source: — Problem Solving |
Master | Next Rank: 500 Posts
Posts: 199
Joined: Sat Apr 26, 2014 10:53 am
Thanked: 16 times
Followed by:4 members
GMAT Score:780

by 800_or_bust » Sun Jun 12, 2016 6:04 am
800_or_bust wrote:Can anybody help me with this? It's probably more difficult than anything that would appear on the GMAT. I came up with this question in an attempt to challenge myself, but I'm having a hard time conceptualizing the answer. Any insight is appreciated?

In how many different ways can six unique coins - a penny, a nickel, a dime, a quarter, a half dollar, and a silver dollar - be distributed among three people, such that each coin is distributed and each person receives at least one coin?
If we just wanted to select three coins from six, it would be 6C3 = 20. However, the distribution adds a layer of complexity that makes this problem extremely difficult. The numbers seem nice and small, but when you think about it, it's very tricky.

There are 90 different ways to do this in the case where any two of the people receive exactly one coin. For instance, if Person #1 receives a penny, there are five different ways to distribute one coin to Person #2 with Person #3 receiving the remaining four coins. This is true for all six coins, so there are 5x6 = 30 ways Person #1 and Person #2 can receive one coin. Likewise, there are 5x6 = 30 ways, Person #1 and Person #3 can receive one coin each. And 5x6 = 30 different ways Person #2 and Person #3 can receive one coin each. Maybe this problem is just too difficult to solve? Are there any shortcuts to solving this, or is this problem not solvable by any ordinary approach to combinatorics?
800 or bust!
Top
User avatar
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 » Sun Jun 12, 2016 2:56 pm
800_or_bust wrote:In how many different ways can six unique coins - a penny, a nickel, a dime, a quarter, a half dollar, and a silver dollar - be distributed among three people, such that each coin is distributed and each person receives at least one coin?
Let the 3 people be A, B and C.

Total possible distributions:
Number of options for the penny = 3. (A, B or C)
Number of options for the nickel = 3. (A, B or C)
Number of options for the dime = 3. (A, B or C)
Number of options for the quarter = 3. (A, B or C)
Number of options for the half-doller = 3. (A, B or C)
Number of options for the silver dollar = 3. (A, B or C)
To combine these options, we multiply:
3*3*3*3*3*3 = 729.

Bad distributions: A, B or C receives no coins
Number of options for the person receiving no coins = 3. (A, B or C)
Number of options for the penny = 2. (Either of the 2 remaining people)
Number of options for the nickel = 2. (Either of the 2 remaining people)
Number of options for the dime = 2. (Either of the 2 remaining people)
Number of options for the quarter = 2. (Either of the 2 remaining people)
Number of options for the half-doller = 2. (Either of the 2 remaining people)
Number of options for the silver dollar = 2. (Either of the 2 remaining people)
To combine these options, we multiply:
3*2*2*2*2*2*2 = 192.

Total possible distributions - bad distributions = 729-192 = 537.

But wait!
Now we must account for some OVERLAPS.
The bad distributions subtracted above are composed of the following:

Bad distribution 1: A = no coins
There are 3 ways for A to receive no coins:
A = no coins, B = at least 1 coin, C = at least 1 coin
A = no coins, B = no coins, C = all the coins
A = no coins, B = all the coins, C = no coins

Bad distribution 2: B = no coins
There are 3 ways for B to receive no coins:
B = no coins, A = at least 1 coin, C = at least 1 coin
B = no coins, A = no coins, C = all the coins
B = no coins, A = all the coins, C = no coins

Bad distribution 3: C = no coins
There are 3 ways for C to receive no coins:
C = no coins, A = at least 1 coin, B = at least 1 coin
C = no coins, A = no coins, B = all the coins
C = no coins, A = all the coins, B = no coins

Notice the following:
When we subtracted bad distributions 1, 2 and 3 from the total, the red case, the blue case, and the green case were each subtracted from the total TWICE.
Since each colored case was subtracted twice, each must now be added BACK into the total.

Adding the 3 colored cases back into the total, we get:
537+3 = 540.
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
Top
Master | Next Rank: 500 Posts
Posts: 199
Joined: Sat Apr 26, 2014 10:53 am
Thanked: 16 times
Followed by:4 members
GMAT Score:780

by 800_or_bust » Mon Jun 13, 2016 3:38 am
GMATGuruNY wrote:
800_or_bust wrote:In how many different ways can six unique coins - a penny, a nickel, a dime, a quarter, a half dollar, and a silver dollar - be distributed among three people, such that each coin is distributed and each person receives at least one coin?
Let the 3 people be A, B and C.

Total possible distributions:
Number of options for the penny = 3. (A, B or C)
Number of options for the nickel = 3. (A, B or C)
Number of options for the dime = 3. (A, B or C)
Number of options for the quarter = 3. (A, B or C)
Number of options for the half-doller = 3. (A, B or C)
Number of options for the silver dollar = 3. (A, B or C)
To combine these options, we multiply:
3*3*3*3*3*3 = 729.

Bad distributions: A, B or C receives no coins
Number of options for the person receiving no coins = 3. (A, B or C)
Number of options for the penny = 2. (Either of the 2 remaining people)
Number of options for the nickel = 2. (Either of the 2 remaining people)
Number of options for the dime = 2. (Either of the 2 remaining people)
Number of options for the quarter = 2. (Either of the 2 remaining people)
Number of options for the half-doller = 2. (Either of the 2 remaining people)
Number of options for the silver dollar = 2. (Either of the 2 remaining people)
To combine these options, we multiply:
3*2*2*2*2*2*2 = 192.

Total possible distributions - bad distributions = 729-192 = 537.

But wait!
Now we must account for some OVERLAPS.
The bad distributions subtracted above are composed of the following:

Bad distribution 1: A = no coins
There are 3 ways for A to receive no coins:
A = no coins, B = at least 1 coin, C = at least 1 coin
A = no coins, B = no coins, C = all the coins
A = no coins, B = all the coins, C = no coins

Bad distribution 2: B = no coins
There are 3 ways for B to receive no coins:
B = no coins, A = at least 1 coin, C = at least 1 coin
B = no coins, A = no coins, C = all the coins
B = no coins, A = all the coins, C = no coins

Bad distribution 3: C = no coins
There are 3 ways for C to receive no coins:
C = no coins, A = at least 1 coin, B = at least 1 coin
C = no coins, A = no coins, B = all the coins
C = no coins, A = all the coins, B = no coins

Notice the following:
When we subtracted bad distributions 1, 2 and 3 from the total, the red case, the blue case, and the green case were each subtracted from the total TWICE.
Since each colored case was subtracted twice, each must now be added BACK into the total.

Adding the 3 colored cases back into the total, we get:
537+3 = 540.
Thanks for the response! This was a very nice approach - I didn't think to look at it from the perspective of the coins.

I actually did come up with a solution eventually. I approached it as four possible cases - Case 1, where person A receives one coin; Case 2, where person A receives two coins; Case 3, where person A receives three coins; and Case 4, where person A receives four coins. Note we only need to consider all of the possibilities of Persons A & B, because once they are set, Person C's coin configuration is fixed.

There are 6-choose-1 different ways that Person A can get one coin. Person B can receive anywhere from 1 to 4 coins from the remaining 5 coins - so sum together 5C1 + 5C2 + 5C3 + 5C4, and multiply the two stages together. Then repeat this for each of the four cases.

Then total number of possibilities is: 6C1 (5C1 + 5C2 + 5C3 + 5C4) + 6C2 (4C1 + 4C2 + 4C3) + 6C3 (3C1 + 3C2) + 6C4 (2C1) = 6 (5 + 10 + 10 + 5) + 15 (4 + 6 + 4) + 20 (3 + 3) + 15 (2) = 180 + 210 + 120 + 30 = 540!
800 or bust!
Top
GMAT Instructor
Posts: 2630
Joined: Wed Sep 12, 2012 3:32 pm
Location: East Bay all the way
Thanked: 625 times
Followed by:119 members
GMAT Score:780

by Matt@VeritasPrep » Thu Jun 23, 2016 5:29 pm
This is a pretty standard problem in the first week of an undergrad probability class: the setup is usually marbles being distributed into boxes, with the crucial factors being:

(i) whether the marbles are identical, the boxes are identical, both, or neither;
(ii) whether any of the boxes can be empty

Here's a primer. (I don't know if it's any good, I just linked to the first one I found on Google. I first learned this concept in Sam Chiu's great intro to probability textbook, but it doesn't seem to be available online. :/)

As you can see from that link, this is a special case of Theorem 2: when we're distributing n distinguishable marbles into k distinguishable boxes, there are k� arrangements, so we start with

n = 6, k = 3, k� = 3� = 729

From there, we need to eliminate the cases in which at least one person receives no coins.

If Person A alone gets no coins, we have n = 6, k = 2, k� = 2� = 64. Same for Persons B and C, so that gives us 192 bad cases.

Unfortunately, there's some overlap here. The case in which A gets no coins contains "B gets all 6" and "C gets all 6"; the case in which B gets no coins contains "A gets all 6" and "C gets all 6"; and the case in which C gets no coins contains "A gets all 6" and "B gets all 6". Each case in which one person gets all 6 was subtracted TWICE, but we only wanted to subtract each case ONCE.

Adding those three cases back in, we get

729 - 192 + 3, or 540.

It might be easier to see this as

3� - 3*2� + 3*1�

which is a pretty nice piece of PIE! :D (... and one that gives you a sense of the form of a general solution to this problem, given any number of distinct coins and any number of people)
Top
Post new topic Post Reply
• Page 1 of 1