Unfair Distributions in Combinatorics - Part II
BY KARISHMA, VERITAS PREP
Solution: We have 5 identical apples and 4 children. We want to find the number of ways in which these apples can be distributed among the children.
Method I5 apples can be distributed in various ways: {5, 0, 0, 0}, {4, 1, 0, 0}, {3, 2, 0, 0}, {3, 1, 1, 0}, {2, 2, 1, 0}, {2, 1, 1, 1}.
{5, 0, 0, 0} means that one child gets all 5 apples and all others get none. Similarly, {4, 1, 0, 0} means that one child gets 4 apples and another child gets 1 apple. No one else gets any apples and so on…
In each one of these cases, various arrangements are possible e.g. take the case of {5, 0, 0, 0}. The first child could get all 5 apples OR the second child could get all 5 apples OR the third child could get all 5 apples OR the fourth child could get all 5 apples. Basically, the number of ways in which these 4 objects – 5, 0, 0 and 0 can be distributed in 4 different spots (i.e. 4 children) is 4!/3! = 4 arrangements (we divide by 3! because three of the objects – 0, 0 and 0 – are identical). This is just our beloved basic counting principle in action.
Similarly, in the case of {4, 1, 0, 0}, we will get 4!/2! = 12 arrangements (since 2 objects are identical) i.e. 5 apples can be distributed among 4 children by giving 4 apples to one child and 1 apple to another child in 12 ways. The first child could get 4 apples and the second child could get 1 apple OR the third child could get 4 apples and the first child could get 1 apple etc.
In the same way, we will get 12 arrangements in each one of these cases: {3, 2, 0, 0}, {3, 1, 1, 0} and {2, 2, 1, 0}. In the case of {2, 1, 1, 1}, we will get 4!/3! = 4 arrangements.
In all, 5 identical apples can be distributed among 4 children in 4 + 12 + 12 + 12 + 12 + 4 = 56 ways
Here, we have just counted out the ways in which 5 things can be distributed in 4 groups. If we miss even one of these cases, all our effort would go waste. Therefore, let’s look at a more analytical method of solving this question.
Method IILet’s put the 5 apples in a row: A A A A A
We have to split them in 4 groups. The 4 groups will have a one-to-one relation with the 4 children – Apples in the first group will be given to the first child, those in the second group will be given to the second child and so on…
Say we split the apples in 4 groups in the following way: A A l A l A l A
The vertical lines separate one group from the other. The first group has 2 apples and the rest of the three groups have 1 apple each. This means, the first child gets 2 apples and each of the other 3 children get 1 apple each.
The split can also be made in the following way: A l A A l A l A
Here, the second group has 2 apples and the rest of the three groups have 1 apple each. So the second child gets 2 apples and the rest of the 3 children get 1 apple each.
The split can also be made in the following way: l A A A l A l A
Here, the first group has no apples, the second group has 3 apples and the third and the fourth groups have one apple each. The first child gets no apples, the second child gets 3 apples and the other 2 children get 1 apple each.
What I am trying to show here is that arranging these 5 identical As and the 3 identical vertical lines in as many different ways as possible will give us all the ways in which we can distribute 5 identical apples among 4 different children.
In how many different ways can we arrange these 8 objects i.e. 5 identical As and 3 identical vertical lines? In 8!/(5! * 3!) = 56 ways
Question 4: In how many ways can 5 apples (identical) be distributed among 4 identical baskets?Solution: As we have seen previously, 5 fruits can be split into 4 groups in the following ways: {5, 0, 0, 0}, {4, 1, 0, 0}, {3, 2, 0, 0}, {3, 1, 1, 0}, {2, 2, 1, 0}, {2, 1, 1, 1}
Here, {5, 0, 0, 0} means that one basket has all 5 apples and the rest of the baskets are empty. Since the baskets are all identical, there is only 1 way of doing this.
{4, 1, 0, 0} means that one basket has 4 apples, another one has 1 apple and the rest of the baskets are empty. Since the fruits and the baskets are all identical, there is again only 1 way of doing this.
You have to select neither the fruits nor the baskets since they are all identical. You only have to decide how to distribute the apples in 4 groups. Therefore, each one of these cases will give us only one different way of distributing the fruits. Since there are 6 such cases, there are only 6 different ways of distributing the fruits.
I wouldn’t be surprised if you are a little confused at this point since the different variations change the thought process completely. That is the whole fun of combinatorics. You change one word and we have to start thinking from the scratch. You miss one word and you either don’t realize at all that your answer is wrong (if the options are cunning) or you realize after you have solved the entire question. Thankfully, GMAT has only one to two questions based on this topic.
thanks for the comprehensive explanation. I have a quick question regarding the vertical line method. Above Bunuel showed to examples with 5 identical fruit distributed to 1) 4 children, 2) 4 baskets.
-> Why is not possible in Case 2 (baskets) to simply unarrange the arrangement for boys, i.e. use vertical line method \(\frac{8!}{(5!*3!)}\) -> unarrange by multiplying with \(\frac{1}{4!}\). This results obviously in a non-sensical number and not 6 as it should.