Thread: Paradox in combinations?

Here's an innocent-looking question:

There are 4 girls and 7 boys. How many ways can we select a team of 5, such that at least 3 members are girls?

One way to solve this is to consider the cases when there are exactly 3 girls and exactly 4 girls in the team.
So, when there are exactly 3 girls, # of ways = C(4,3)*C(7,2)= 4*21 = 84
And when there are exactly 4 girls, # of ways= C(4,4)*C(7,1)= 1*7 = 7
And no we just add them up, so total # of ways to select a team with at least 3 girls = 84+7 = 91

Simple enough...... but

Suppose I take it this way: There need to be at least 3 girls in the team. These three girls can be selected in C(4,3) = 4 ways.
Now, we have 2 vacancies in the team, and 8 people (7 boys + the girl left out) who can fill it. So we can select these 2 team members in C(8,2)= 28 ways.
Thus the total number of ways to select a team should be 4*28 = 112

What's going wrong??

I've tried a few more questions like this, and the solutions given by these two methods never match up.... What gives?

Originally Posted by Arcturus

There are 4 girls and 7 boys. How many ways can we select a team of 5, such that at least 3 members are girls?

One way to solve this is to consider the cases when there are exactly 3 girls and exactly 4 girls in the team.
So, when there are exactly 3 girls, # of ways = C(4,3)*C(7,2)= 4*21 = 84
And when there are exactly 4 girls, # of ways= C(4,4)*C(7,1)= 1*7 = 7
And no we just add them up, so total # of ways to select a team with at least 3 girls = 84+7 = 91
Suppose I take it this way: There need to be at least 3 girls in the team. These three girls can be selected in C(4,3) = 4 ways.
Now, we have 2 vacancies in the team, and 8 people (7 boys + the girl left out) who can fill it. So we can select these 2 team members in C(8,2)= 28 ways.
Thus the total number of ways to select a team should be 4*28 = 112
What's going wrong??
I've tried a few more questions like this, and the solutions given by these two methods never match up.... What gives?

They can never match! In the second way you have counted the same girl several times.

Say the girls are {A,B,C,D}, the boys {P,Q,R....}.
According to your second method we can pick {A,C,D} {B,Q} one time.
The next selection could be {A,B,C} {D,Q}.
There is two different ways to select the same team counting it twice.

Originally Posted by Plato

They can never match! In the second way you have counted the same girl several times.

Say the girls are {A,B,C,D}, the boys {P,Q,R....}.
According to your second method we can pick {A,C,D} {B,Q} one time.
The next selection could be {A,B,C} {D,Q}.
There is two different ways to select the same team counting it twice.

@Arcturus - When I started with this subject, I faced the exact problem mentioned by you. And, even today it keeps coming back as I try little more complicated problems.

One thing that worked for me, and might help you as well is follows -
Try to establish that the actual outputs in the questions have a one-one onto mapping with the counting logic you are using.

As Plato demonstrated in your argment this was not applicable.

The above approach also helps a lot in honing your skills at coming up with counting arguments. This really helped me, so thought will share with you.

Originally Posted by Plato

They can never match! In the second way you have counted the same girl several times.

Say the girls are {A,B,C,D}, the boys {P,Q,R....}.
According to your second method we can pick {A,C,D} {B,Q} one time.
The next selection could be {A,B,C} {D,Q}.
There is two different ways to select the same team counting it twice.

Thanks a lot! That really clears things up.

Originally Posted by aman_cc

@Arcturus - When I started with this subject, I faced the exact problem mentioned by you. And, even today it keeps coming back as I try little more complicated problems.

One thing that worked for me, and might help you as well is follows -
Try to establish that the actual outputs in the questions have a one-one onto mapping with the counting logic you are using.

As Plato demonstrated in your argment this was not applicable.

The above approach also helps a lot in honing your skills at coming up with counting arguments. This really helped me, so thought will share with you.

Thanks for the advice, I'll keep that in mind.