Clarification needed on combinatorics problem

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

knight247: Legendary Member; Posts: 504; Joined: Tue Apr 19, 2011 1:40 pm; Thanked: 114 times; Followed by:11 members

Clarification needed on combinatorics problem

by knight247 » Fri Nov 21, 2014 10:03 am

In how many ways can 16 different gifts be divided among four children such that each child receives exactly four gifts?

OA [spoiler]16! Ã· (4!)^4[/spoiler]

I already got the answer by doing 16C4 * 12C4 * 8C4 * 4C4

My question is, since the four children are NOT identical, shouldn't the above calculation also have a 4C1*3C1*2C1 in there? Considering the four children are NOT identical, we would need to pick one kid each time we need to assign a kid an assortment of four gifts, don't we?

Detailed explanations would be appreciated. Many thanks in advance.

Quote

Source: Beat The GMAT — Problem Solving | Fri Nov 21, 2014 10:03 am

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 » Fri Nov 21, 2014 10:14 am

knight247 wrote:In how many ways can 16 different gifts be divided among four children such that each child receives exactly four gifts?

I already got the answer by doing 16C4 * 12C4 * 8C4 * 4C4.

Your solution is correct.
Let the four children be Adam, Bobby, Cindy and David.
From 16 gifts, the number of ways to choose 4 to give to Adam = 16C4.
From the remaining 12 gifts, the number of ways to choose 4 to give to Bobby = 12C4.
From the remaining 8 gifts, the number of ways to choose 4 to give to Cindy = 8C4.
From the remaining 4 gifts, the number of ways to choose 4 to give to David = 4C4.
To combine these options, we multiply:
16C4 * 12C4 * 8C4 * 4C4.

Last edited by GMATGuruNY on Thu Oct 15, 2015 11:11 am, edited 1 time in total.

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

Quote

GMAT/MBA Expert

Brent@GMATPrepNow: GMAT Instructor; Posts: 16207; Joined: Mon Dec 08, 2008 6:26 pm; Location: Vancouver, BC; Thanked: 5254 times; Followed by:1268 members; GMAT Score:770

by Brent@GMATPrepNow » Fri Nov 21, 2014 10:17 am

knight247 wrote:In how many ways can 16 different gifts be divided among four children such that each child receives exactly four gifts?

If we take the task of distributing the 16 gifts and break it into stages, we can see that we need not perform the additional calculations you suggest.

Let's say the children are named A, B, C, and D

Stage 1: Select 4 gifts to give to child A
Since the order in which we select the 4 gifts does not matter, we can use combinations.
We can select 4 gifts from 16 gifts in 16C4 ways (= 16!/(4!)(12!))
So, we can complete stage 1 in 16!/(4!)(12!) ways

Stage 2: select 4 gifts to give to child B
There are now 12 gifts remaining
Since the order in which we select the 4 gifts does not matter, we can use combinations.
We can select 4 gifts from 12 gifts in 12C4 ways (= 12!/(4!)(8!))
So, we can complete stage 2 in 12!/(4!)(8!) ways

Stage 3: select 4 gifts to give to child C
There are now 8 gifts remaining
We can select 4 gifts from 8 gifts in 8C4 ways (= 8!/(4!)(4!))
So, we can complete stage 3 in 8!/(4!)(4!) ways

Stage 4: select 4 gifts to give to child C
There are now 4 gifts remaining
NOTE: There's only 1 way to select 4 gifts from 4 gifts, but if we want the answer to look like the official answer, let's do the following:
We can select 4 gifts from 4 gifts in 4C4 ways (= 4!/4!)
So, we can complete stage 4 in 4!/4! ways

By the Fundamental Counting Principle (FCP), we can complete all 4 stages (and thus distribute all 16 gifts) in [16!/(4!)(12!)][12!/(4!)(8!)][8!/(4!)(4!)][4!/4!] ways

A BUNCH of terms cancel out to give us ([spoiler]= 16!/(4!)â�´[/spoiler])

--------------------------

Note: the FCP can be used to solve the MAJORITY of counting questions on the GMAT. For more information about the FCP, watch our free video: https://www.gmatprepnow.com/module/gmat-counting?id=775

Then you can try solving the following questions:

EASY
- https://www.beatthegmat.com/what-should- ... 67256.html
- https://www.beatthegmat.com/counting-pro ... 44302.html
- https://www.beatthegmat.com/picking-a-5- ... 73110.html
- https://www.beatthegmat.com/permutation- ... 57412.html
- https://www.beatthegmat.com/simple-one-t270061.html
- https://www.beatthegmat.com/mouse-pellets-t274303.html

MEDIUM
- https://www.beatthegmat.com/combinatoric ... 73194.html
- https://www.beatthegmat.com/arabian-hors ... 50703.html
- https://www.beatthegmat.com/sub-sets-pro ... 73337.html
- https://www.beatthegmat.com/combinatoric ... 73180.html
- https://www.beatthegmat.com/digits-numbers-t270127.html
- https://www.beatthegmat.com/doubt-on-sep ... 71047.html
- https://www.beatthegmat.com/combinatoric ... 67079.html

DIFFICULT
- https://www.beatthegmat.com/wonderful-p- ... 71001.html
- https://www.beatthegmat.com/ps-counting-t273659.html
- https://www.beatthegmat.com/permutation- ... 73915.html
- https://www.beatthegmat.com/please-solve ... 71499.html
- https://www.beatthegmat.com/no-two-ladie ... 75661.html
- https://www.beatthegmat.com/laniera-s-co ... 15764.html

Cheers,
Brent

Brent Hanneson - Creator of GMATPrepNow.com

Quote

prada: Senior | Next Rank: 100 Posts; Posts: 64; Joined: Wed Dec 08, 2010 10:55 pm; Thanked: 1 times

by prada » Thu Oct 15, 2015 11:01 am

GMATGuruNY wrote:
knight247 wrote:In how many ways can 16 different gifts be divided among four children such that each child receives exactly four gifts?

I already got the answer by doing 16C4 * 12C4 * 8C4 * 4C4.
Your solution is correct.
Let the four children be Adam, Bobby, Cindy and David.
From 16 gifts, the number of ways to choose 4 to give to Adam = 16C4.
From the remaining 12 gifts, the number of ways to choose 4 to give to Bobby = 12C4.
From the remaining 8 gifts, the number of ways to choose 4 to give to Cindy = 8C4.
From the remaining 4 gifts, the number of ways to choose 4 to give to David = 4C4.
To combine these options, we multiply:
16C4 * 12C5 * 8C4 * 4C4.

Hey Mitch on your last line I believe you mean 12C4 and not 12C5?

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 » Thu Oct 15, 2015 11:14 am

prada wrote: Hey Mitch on your last line I believe you mean 12C4 and not 12C5?

Thanks for pointing out the typo.
I've amended my solution accordingly.

Quote

Dutta: Newbie | Next Rank: 10 Posts; Posts: 2; Joined: Sun Jan 31, 2016 10:32 pm

by Dutta » Mon Feb 08, 2016 9:54 am

Hey Brent,

Since the 4 kids are not identical should we not consider selecting as to who receives the 1st set of 4 gifts and who the 2nd and so on. So shouldn't the ans be multiplied by a 4!?

Brent@GMATPrepNow wrote:
knight247 wrote:In how many ways can 16 different gifts be divided among four children such that each child receives exactly four gifts?

If we take the task of distributing the 16 gifts and break it into stages, we can see that we need not perform the additional calculations you suggest.

Let's say the children are named A, B, C, and D

Stage 1: Select 4 gifts to give to child A
Since the order in which we select the 4 gifts does not matter, we can use combinations.
We can select 4 gifts from 16 gifts in 16C4 ways (= 16!/(4!)(12!))
So, we can complete stage 1 in 16!/(4!)(12!) ways

Stage 2: select 4 gifts to give to child B
There are now 12 gifts remaining
Since the order in which we select the 4 gifts does not matter, we can use combinations.
We can select 4 gifts from 12 gifts in 12C4 ways (= 12!/(4!)(8!))
So, we can complete stage 2 in 12!/(4!)(8!) ways

Stage 3: select 4 gifts to give to child C
There are now 8 gifts remaining
We can select 4 gifts from 8 gifts in 8C4 ways (= 8!/(4!)(4!))
So, we can complete stage 3 in 8!/(4!)(4!) ways

Stage 4: select 4 gifts to give to child C
There are now 4 gifts remaining
NOTE: There's only 1 way to select 4 gifts from 4 gifts, but if we want the answer to look like the official answer, let's do the following:
We can select 4 gifts from 4 gifts in 4C4 ways (= 4!/4!)
So, we can complete stage 4 in 4!/4! ways

By the Fundamental Counting Principle (FCP), we can complete all 4 stages (and thus distribute all 16 gifts) in [16!/(4!)(12!)][12!/(4!)(8!)][8!/(4!)(4!)][4!/4!] ways

A BUNCH of terms cancel out to give us ([spoiler]= 16!/(4!)â�´[/spoiler])

--------------------------

Note: the FCP can be used to solve the MAJORITY of counting questions on the GMAT. For more information about the FCP, watch our free video: https://www.gmatprepnow.com/module/gmat-counting?id=775

Then you can try solving the following questions:

EASY
- https://www.beatthegmat.com/what-should- ... 67256.html
- https://www.beatthegmat.com/counting-pro ... 44302.html
- https://www.beatthegmat.com/picking-a-5- ... 73110.html
- https://www.beatthegmat.com/permutation- ... 57412.html
- https://www.beatthegmat.com/simple-one-t270061.html
- https://www.beatthegmat.com/mouse-pellets-t274303.html

MEDIUM
- https://www.beatthegmat.com/combinatoric ... 73194.html
- https://www.beatthegmat.com/arabian-hors ... 50703.html
- https://www.beatthegmat.com/sub-sets-pro ... 73337.html
- https://www.beatthegmat.com/combinatoric ... 73180.html
- https://www.beatthegmat.com/digits-numbers-t270127.html
- https://www.beatthegmat.com/doubt-on-sep ... 71047.html
- https://www.beatthegmat.com/combinatoric ... 67079.html

DIFFICULT
- https://www.beatthegmat.com/wonderful-p- ... 71001.html
- https://www.beatthegmat.com/ps-counting-t273659.html
- https://www.beatthegmat.com/permutation- ... 73915.html
- https://www.beatthegmat.com/please-solve ... 71499.html
- https://www.beatthegmat.com/no-two-ladie ... 75661.html
- https://www.beatthegmat.com/laniera-s-co ... 15764.html

Cheers,
Brent

Quote

GMAT/MBA Expert

Brent@GMATPrepNow: GMAT Instructor; Posts: 16207; Joined: Mon Dec 08, 2008 6:26 pm; Location: Vancouver, BC; Thanked: 5254 times; Followed by:1268 members; GMAT Score:770

by Brent@GMATPrepNow » Mon Feb 08, 2016 1:50 pm

Dutta wrote:Hey Brent,

Since the 4 kids are not identical should we not consider selecting as to who receives the 1st set of 4 gifts and who the 2nd and so on. So shouldn't the ans be multiplied by a 4!?

We have already accounted for the children being non-identical.
At each stage, we give gifts to a particular child (child A, B, C and D)

Cheers,
Brent

Brent Hanneson - Creator of GMATPrepNow.com