Quarter Wit, Quarter Wisdom: Unfair Distributions in Combinatorics - Part II

Quarter Wit, Quarter WisdomToday’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!

Karishma, a Computer Engineer with a keen interest in alternative Mathematical approaches, has mentored students in the continents of Asia, Europe and North America. She teaches the GMAT for Veritas Prep and regularly participates in content development projects such as this blog!

6 Responses

  1. stne says:

    Karishma

    Thank you for hitting the bulls eye once again, when I saw the exact same question in GC I was myself wondering , about the same things being distributed among same things case.

    case 4 above.

    Also I was wondering about the different things being distributed among the same things

    Case 3 above.

    The ring question looks like an exception kind.

    The more general kinds of question are:
    when identical things are being distributed among different persons or things
    n+r-1 C r-1

    where n same kind of things are being distributed among r different people/things and each can get 0,1 or more things.

    and different kinds of fruit / things are being distributed among different baskets/ things
    question 1 in part 1.( as long as the different things are not not rings,or ring like items)

    we can use n^x where n different things ( fruits )are being distributed and they are being distributed among x different things( basket ).

    Thank you for such a wonderful article.

    • Karishma says:

      Let me point out that the concepts discussed here are advanced. The probability that you will see them in the actual exam is low. The articles are meant to be an intellectual exercise in P&C – how to think in different situations, what different methodologies you can use etc. So even though it feels good to know the fix-it formula for a particular situation, I doubt there is much to gain from learning it. If you understand the concepts discussed here, there is of course no harm in keeping them in mind. But if you plan to do that, ensure that you understand the formula i.e. the exact situations in which it can be used.

  2. stne says:

    oops! Got myself confused here .

    n^x should be x^n above where n different things ( fruits )are being distributed and they are being distributed among x different things( basket ).

    The question will clarify this.

    Distribute 5 different fruits among 4 different children.

    4^5

  3. Santhosh says:

    Hi Karishma,

    In how many ways can 5 different fruits be distributed among 4 identical baskets?

    You have showed us how to solve the above problem using brute force method.Kindly explain how to solve the problem more analytically.

    I tried solving analytically but couldn’t get anywhere closer.

  4. santhosh says:

    Hi Karishma,

    In how many ways can 5 different fruits be distributed among 4 identical baskets?

    If there is an analytical and direct method to solve the above problem.Please share it.

    I checked In Gmatclub forum also but even there the problem was solved using only the brute force method.

    I’m just trying to learn the intuitive way of solving the problem.

    • Karishma says:

      When the objects you are distributing are identical, you can use some analytical methods (as discussed in the last post). When the recipients are identical, you generally need to use brute force only.

Leave a Reply

Spam protection by WP Captcha-Free