Problem Solving

brianlange77 wrote:

2mist wrote:Hi Brent,

I am not sure how to put my doubt in words, but I hope you will get a faint idea of what I am talking about and help me, and alike, out in understanding the concept.

1. Some times when we say order doesn't matter, we divide the the factorial : -

eg:

picking 2 members from a group of 5 (A, B, C, D, E) members :

(5x4)/ 2 we divide by 2 here because A and B can occur in any order i.e AB and BA both are same.


2. Some times when we have to take into account that items can appear in any order, we multiply a factorial ( doing so, according to me, also means order doesn't matter)

eg.

if we have 5 different balls to distribute in 3 different baskets we can do it in following ways

(3 * 1 * 1) *3---here we are multiplying the factorial by 3 because order doesn't matter and 3 balls can be placed in any of the basket.

or

(2*2*1)*3 ---here we are multiplying the factorial by 3 because order doesn't matter and 2 balls can be placed in any of the 2 baskets out of 3.

There is some huge confusion here. Please help me understand the logic.

Thanks,
Mist

Mist -- to address your question, let me ask you this. Is your question about the mathematical steps themselves? Or is it about understanding the situations when 'order' does matter vis a vis those situations when it doesn't matter? More than happy to help either way -- but wanted to make sure I (or others) can answer your REAL question!
Thanks,
Brian

2mist wrote:

brianlange77 wrote:

2mist wrote:Hi Brent,

I am not sure how to put my doubt in words, but I hope you will get a faint idea of what I am talking about and help me, and alike, out in understanding the concept.

1. Some times when we say order doesn't matter, we divide the the factorial : -

eg:

picking 2 members from a group of 5 (A, B, C, D, E) members :

(5x4)/ 2 we divide by 2 here because A and B can occur in any order i.e AB and BA both are same.


2. Some times when we have to take into account that items can appear in any order, we multiply a factorial ( doing so, according to me, also means order doesn't matter)

eg.

if we have 5 different balls to distribute in 3 different baskets we can do it in following ways

(3 * 1 * 1) *3---here we are multiplying the factorial by 3 because order doesn't matter and 3 balls can be placed in any of the basket.

or

(2*2*1)*3 ---here we are multiplying the factorial by 3 because order doesn't matter and 2 balls can be placed in any of the 2 baskets out of 3.

There is some huge confusion here. Please help me understand the logic.

Thanks,
Mist

Mist -- to address your question, let me ask you this. Is your question about the mathematical steps themselves? Or is it about understanding the situations when 'order' does matter vis a vis those situations when it doesn't matter? More than happy to help either way -- but wanted to make sure I (or others) can answer your REAL question!
Thanks,
Brian

Hi Brian,

Thanks for your quick response.

I don't have problem understanding the mathematical steps involved in solving either of the question. I understand when to use combination and when to use permutation, Yet I feel there is some gap.

I don't understand why sometimes we multiply to take into account that the ball, or for that matter any thing, can appear in either of the three places.
eg.
3 balls can be placed in 1st or 2nd or 3rd basket so we multiply by 3.

where as, we generally apply combination to take into account that order doesn't matter, dividing the factorial rather than multiplying.

May be a few questions, with good explanation, where we use the latter will hep solidify my understanding, coz i am confident about combination technique.

Regards,
Mist

Brent@GMATPrepNow wrote:Hi Mist,

I'd like to jump in and mention that I recently wrote an article on this topic: https://www.beatthegmat.com/mba/2013/09/ ... s-part-iii
This article is part III in a 3-part series examining counting techniques.

Here are parts I and II as well:
- https://www.beatthegmat.com/mba/2013/07/ ... ons-part-i
- https://www.beatthegmat.com/mba/2013/08/ ... ns-part-ii

Cheers,
Brent

HI Brent,

I have been using FCP concepts for solving counting problem and they have indeed made my life easier. However, your articles on this topic are awesome and have solidified my understanding of this topic even further.

"Does the outcome of one stage differ from the outcome of the other stage?" -- did give me an aha moment today..i will make sure I narrate my kids how uncle Brent helped their daddy get into a MBA college, helping meet their mother and thus in a way, are responsible for their existence.


Having said that, I do have few doubts and will greatly appreciate your input.

1.
From the set of integers from 1 to 100 inclusive, in how many ways can we select two different numbers such that their sum is an EVEN integer?

To solve this shouldn't we consider two cases:

a. select an even number * select an odd number = 50*50 = 2500
OR
b. select an odd number * select an even number = 50*50 = 2500

answer = 5000 ( you have derived the answer 2500, considering only case 'a' )

2. If my above understanding is wrong, then what are the situations in which we apply such cases?


Please help me solve these two problems in your approach. I don't have problem in understanding the steps involved; however, I believe by reading your solution I will gain further insight.

3. In how many ways you can distribute 5 marbles in 3 identical baskets such that each basket has at least one marble.

4. In how many ways you can distribute 5 different coloured marbles in 3 distinct baskets such that each basket has at least one marble.

Regards,
Mist

Now let's try a harder question.

From the set of integers from 1 to 100 inclusive, in how many ways can we select two different numbers such that their sum is an odd integer?

Let's first see what happens when we ask, "Does the order of the two selected numbers matter?"

Well, selecting 7 then 20 (for an odd sum of 27) is the same as selecting 20 then 7. Since the order doesn't matter, this must be a combination question, right?

No. It turns out that this is not a combination question, even though it appears that order doesn't matter.

Now let's see what happens when we apply the FCP.

We'll take the task of selecting 2 numbers (with an odd sum), and we'll break it into stages. One way to do this is to first recognize that, for the sum to be odd, one number must be even, and the other number must be odd. So, our two stages could look like this:

Stage 1: Select an even number from the set

Stage 2: Select an odd number from the set

Does the outcome of one stage differ from the outcome of the other stage?

YES. In one stage we're selecting an even number, and in the other stage, we're selecting an odd number. Since the outcomes are different, we can continue applying the FCP.

We can complete stage 1 in 50 ways (since there are 50 even numbers in the set), and we can complete stage 2 in 50 ways (since there are 50 odd numbers in the set). By the FCP, we can complete both stages (and thus select 2 numbers with an odd sum) in (50)(50) ways ( = 2500 ways).