Unfair Distributions in Combinatorics - Part II
BY KARISHMA, VERITAS PREP
Today’s post is a continuation of last week’s post and heavily refers back to it. I would suggest you to take a quick look at last week’s post again to make sense of this post. Let’s start with the variation question 1a we saw in the last post.
Question 1a: In how many ways can 5 different rings be worn in four particular fingers? (Some fingers may get more than one ring and some may get no rings.)Solution: The first ring can be worn in 4 ways i.e. in any one of the four fingers. The second ring can be worn in 5 ways (it can go on any one of the four fingers and it can also go below the first ring so there are 5 distinct places for the second ring). The third ring can be worn in 6 ways (any one of the four fingers or below the second ring or below the first ring). The fourth ring can be worn in 7 ways (any one of the four fingers or below the third ring or below the second ring or below the first ring). The fifth ring can be worn in 8 ways (any one of the four fingers or below the fourth ring or below the third ring or below the second ring or below the first ring).
Total number of ways in which 5 different rings can be worn in 4 particular fingers = 4*5*6*7*8.
Compare this with question 1 of last post: In how many ways can 5 different fruits be distributed among four children?
The answer in this case was \(4^5 = 4*4*4*4*4\).
Why are these two questions different? After all, we are distributing 5 different things among 4 children/fingers in both the cases. The difference lies in the fact that when a child gets 2 fruits, the fruits are not arranged but when a finger gets two rings, it gives us 2 different arrangements since the rings can be arranged in 2 ways. You can wear 2 rings on your fingers in 2 different ways (A on top, B at the bottom or B on top and A at the bottom). When you get 2 fruits, there is no arrangement involved. Whether you got fruit A first or fruit B first doesn’t matter. At the end of it, you have 2 fruits A and B and that’s all that matters. In fact this is the reason we cannot solve question 1 using method 2 of question 2 (discussed in the last post). Let’s still try to use it and see why it doesn’t work.
Say, we have 5 different things in a row: A B C D E and 3 identical vertical lines to split these 5 objects into 4 groups. We can arrange these 8 objects, 3 of which are identical, in 8!/3! ways. Notice that 8!/3! = 8*7*6*5*4 i.e. the numbers of ways in which 5 different rings can be worn in 4 fingers. It is not the same as the number of ways in which 5 different fruits can be distributed among 4 children.
We see that:
AB l C l DE
and
BA l C l DE
are two different arrangements. Since how you wear the rings gives you different arrangements, the vertical lines split method can be used to get the answer in the rings question (question 1a). Since these two should not be two different arrangements in case we are talking about distributing fruits among children, this method is not suitable for question 1.I hope I haven’t already confused you. We still have a long way to go!
We should now pay attention to question numbers 3 and 4 from the previous post.
Question 3: In how many ways can 5 different fruits be distributed among 4 identical baskets?Solution: Let’s use the same format as that used in the previous post. 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}
Does it concern us that the baskets are identical? It does. Let’s see how.
{5, 0, 0, 0} means that one basket has all 5 fruits and the rest of the 3 baskets are empty. It doesn’t matter which basket has the fruits because all the baskets are identical. So, this gives us 1 way of distributing the fruits.
{4, 1, 0, 0} means that one basket has 4 fruits, another has the leftover 1 fruit and the other 2 baskets have no fruit. The lone fruit can be chosen in 5 ways. The rest of the 4 fruits will be together in another basket and 2 baskets will be empty. This gives us 5 different ways of distributing the fruits.
{3, 2, 0, 0} means that one basket has 3 fruits, another has the leftover 2 fruits and the other 2 baskets have no fruit. The 3 fruits can be chosen in 5*4*3/3! = 10 ways (= 5C3). The rest of the 2 fruits will be together in another basket in one way and 2 baskets will be empty. This gives us 10 different ways of distributing the fruits.
{3, 1, 1, 0} means that one basket has 3 fruits, another two have a fruit each and the leftover basket has no fruit. The 3 fruits can be chosen in 5*4*3/3! = 10 ways (= 5C3). The rest of the 2 fruits will be in two baskets in one way (since the baskets are all identical) and the last basket will be empty. This gives us 10 different ways of distributing the fruits.
{2, 2, 1, 0} means that 2 baskets have 2 fruits each, one basket has one fruit and the last basket is empty. We can select 1 fruit out of 5 in 5 ways. Now we are left with 4 fruits which have to be split into 2 groups of 2 each. This can be done in 4!/2!*2!*2! = 3 ways (We have already discussed this concept in the post on Groups. Check out the initial theory and question no. 2) This gives us 5*3 = 15 different ways of distributing the fruits.
{2, 1, 1, 1} means that one basket has 2 fruits and the rest of the 3 baskets have a fruit each. We can select 2 fruits out of 5 in 5*4/2! = 10 ways (= 5C2). This gives us 10 different ways of distributing the fruits.
Total number of different ways of distributing the fruits = 1 + 5 + 10 + 10 + 15 + 10 = 51 ways
Something for you to think about: We used the brute force method here. Can we use some more analytical and direct method to solve this question?
Meanwhile, let’s look at question number 4 now.
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.
_________________