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

Quarter Wit, Quarter WisdomToday, using some examples, let’s look at different ways of distributing identical/distinct objects among people or in groups. There are some formulas which can be used in some of these cases but I will only discuss how to use the concepts we have learned so far to deal with these questions. I am not a fan of unintuitive formulas since the probability (we will come to this topic soon) that we will get to use even one of them in GMAT is quite low while the effort involved in cramming all of them is humongous. Therefore, I only want to focus on our core concepts which we can apply in various situations. Let’s start with our first example.

Question 1: In how many ways can 5 different fruits be distributed among four children? (Some children may get more than one fruit and some may get no fruits.)

(A) 4^5
(B) 5^4
(C) 5!
(D) 4!
(E) 4!*5!

Solution 1: This is the simplest case – 5 different things are to be distributed among 4 different people. Say, the five different fruits are: an apple, a banana, a strawberry, an orange and a blueberry. In how many ways can you give an apple to someone? In 4 ways. You can give the apple to any one of the 4 children. Similarly, in how many ways can you give a banana to someone? Again in 4 ways. It is acceptable to give more than one fruit to the same child so you again have 4 possibilities for the banana. Similarly, all the remaining fruits can also be distributed in 4 ways each.

Total number of ways of distributing 5 different fruits among 4 children = 4*4*4*4*4 = 4^5 ways.

Answer (A)

Another popular variation on this type of question is this:

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.)

Here, the answer will be a little different. Think why.

Question 2: In how many ways can 5 apples (identical) be distributed among 4 children? (Some children may get no apples.)

(A) 56
(B) 144
(C) 200
(D) 256
(E) 312

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 I

5 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 II

Let’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

Answer (A).

We have seen how to solve this question in two different ways. A point to note here is that method II cannot be used in question 1 above. Think why.

Now try to solve these two questions:

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

Question 4: In how many ways can 5 apples (identical) be distributed among 4 identical baskets?

We will look at their solutions and the solution of the variation question next week!

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!

21 Responses

  1. Prasath says:

    Hi Karishma,

    i try to find out the difference between Q1 and Q1a. I think the difference is that in Q1a order matters whereas in Q1 it doesn’t. There is no difference if Kid A receives the Banana first and then the Apple or if he/she receives the Apple first and then the Banana.

    When considering the ring example. It does make a difference if RingA ist placed first or second… But I don’t really understand how to consider this. When we use the Fundamental Counting Principle we are essentially saying that one event is succeeded by another event. To come back to our multiple fruit example. We could think of it as Event1: Who should get the Apple? –> 4 possibilities; Event2: Now who should get the Banana? –> 4 possibilities ect. Total ways to distribute the fruits 4*4*…

    Are we still using the Fundamental Counting Principle in the rings example?

  2. Prasath says:

    Q1 = 4^5
    Q1a = 4^5*5!

    ??? Ahhh this makes me crazy -.-

    • Karishma says:

      Try using the basic counting principle for Q1a too. First ring can be worn in __ ways. Second ring in ___ ways etc. My next week’s post will discuss this question and the difference in detail.

  3. Himanshu says:

    Hi Karishma,

    You have asked a question above -
    A point to note here is that method II cannot be used in question 1 above. Think why.

    Can the answer to the above question be that the method that you have described above can be used for IDENTICAL objects only and since question 1 contains different objects, we cannot use it for question 1.

    Please let me know if I am correct.

    Thanks
    H

    • Karishma says:

      Certainly that difference has a role to play but my question is ‘what is the role?’
      What I mean is, why can’t I say that the answer to the first question is 8!/3! using method II of the second question? Why can’t I just get rid of 5! in the denominator since the fruits are all different in question 1?

      • Sri G says:

        Hi Karishma,

        After giving it some thought, I think the issue is the duplicate distributions which we get using 8!/3! for distributing different fruits.

        For example, if we think different apples as A, B, C,D and E then 8!/3! will have duplicates like

        AB|CD|E|
        BA|CD|E|
        BA|DC|E|

  4. The Dark Knight says:

    Karishma,
    For the first problem, why can’t the number of combinations be = 5^4? i.e. every child can get five fruits – i.e. 5X5X5X5 = 5^4?

    Another similiar question – in how many ways can we distribute 5 different balls in 4 boxes? Here, every box can get 5 possible balls => 5^4? Correct?

    Thanks…Please help me……

    • Karishma says:

      You have to distribute fruits which means every fruit must go to some child (though every child may not get a fruit).
      So pick one fruit and you have 4 ways to give it away. Pick another fruit and you again have 4 ways and so on till all 5 fruits are given away. So you get 4^5

      On the other hand, 5^4 implies that you pick up a child and give him a fruit in 5 ways (i.e. one of the 5 fruits). Say you gave an apple to the first child. Then you pick up another child and again give him a fruit in 5 ways (but you don’t have an apple anymore so you have only 4 fruits!). Also, in this case, every child gets exactly one fruit and one fruit will be leftover. That was not what we set out to do. Hence, it cant be 5^4.

      Remember, the thing that you distribute, goes in the power.

      As for the balls boxes problem, again it is the same logic. Every ball must go in a box but a box may be empty. So you have to distribute the balls among the boxes and you can do that in 4^5 ways. (Since there are 5 balls which are to be distributed, 5 is the exponent)

  5. Sri G says:

    Also for question 1a, the difference is that the order of rings matter, so we can use
    Method II here,

    5 rings A,B,C,D and E divided between 4 groups
    ABCDE|||

    So the answer here is 8!/3!= 8*7*6*5*4= 6720

    • Karishma says:

      Correct again!

      • Isha says:

        Hi Karishma,
        A doubt about the comment above – 4 different rings are to be arranged on 4 fingers.
        Isn’t method II about distributing identical things, then how can method II be used with Q1a?
        Method II wil give 8c3=8!/5!*3!

        • Karishma says:

          We are not using Method II as it is to solve this question. We are using a variation according to the changed question. Method II’s logic is that you arrange the things and vertical lines in a row in different ways possible. Since the apples are identical, we say we can arrange them in 8!/5!*3! ways.
          Since the rings are not identical – 5 different rings in 4 fingers – we can arrange them in 8!/3! ways. We don’t need to divide by 5! since the rings are different.

          • Anuj Padia says:

            Hi Karishma,
            For the following question which method do we use to solve and why?
            How many numbers from 1 to 10000 can be made, whose digits add to 5

          • Karishma says:

            All numbers from 1 to 10,000 are accounted for by making 4 digit numbers such that 0 can come anywhere. What this means is that when you account for all numbers such as 0004, 1409, 0065, 0908 etc, you get all 1 digit numbers, all 2 digit numbers, all 3 digit numbers and all 4 digit numbers.

            When you want the sum to be 5, you have five identical 1s in your hand and you need to distribute them to 4 distinct places such that a place may receive no 1s. Now do you see a parallel to one of the questions above?

          • Anuj Padia says:

            The 5 identical apples and 4 children method?
            But why are we use 5 identical ones? and we should be using 4 1s ?
            I am getting confused in this.
            I cant seem to differentiate between the two methods,as in which to use when.

          • Karishma says:

            You need to get the sum of 5. You have 4 distinct places where you can split this 5. e.g.
            2 1 0 2 (leftmost place got two 1s, next got one 1, next got none, next got two 1s)
            0 1 4 0
            5 0 0 0

            Each place is distinct i.e. units place, tens place, hundreds place and thousands place. So 5000 is different from 0005.
            It’s similar to having 4 distinct kids. If you give all to one kid, it is different from giving all to another kid.
            Also, all 1s are identical. When you split the numbers as 4, 1, 0, 0, it doesn’t matter which 1 it is.
            Now does it make sense that this is similar to distributing 5 identical things among 4 distinct people?

          • Anuj Padia says:

            thank you !!
            You have solved one of my major doubts!!
            thank you once again!

  6. Isha says:

    Hi Karishma,

    Can you please provide the link the post next to this one. I am not able to find it.

Leave a Reply

Spam protection by WP Captcha-Free