2
$\begingroup$

In one congress there are 15 physics and 15 math teachers. How many committees of 8 teachers can be formed with at least 4 math teachers and at least 2 physics teachers?

I know how to solve this problem. However. I can't explain why the following solution is incorrect

1)

Commission with 6 mathematicians and 2 physicists:

possibilities to select 4 mathematicians * possibilities to select 2 physicists * possibilities to select the 2 remaining mathematicians from the 11 left: ${14 \choose 4} {15 \choose 2} {11 \choose 2}$

2)

Commission with 4 mathematicians and 4 physicists:

possibilities to select 4 mathematicians * possibilities to select 2 physicists * possibilities to select the 2 remaining physicists from the 13 left:

${15 \choose 4} {15 \choose 2} {13 \choose 2}$

3)

Commission with 5 mathematicians and 3 physicists:

possibilities to select 4 mathematicians * possibilities to select 2 physicists * possibilities to select the 1 remaining mathematicians from the 11 left * possibilities to select the 1 remaining physicists from the 13 left:

${15 \choose 4} {15 \choose 2} {11 \choose 1} {13 \choose 1}$

The answer would then be 1) + 2) + 3).

Why is this solution wrong?

$\endgroup$

5 Answers 5

1
$\begingroup$

The problem is that in general $\binom{n}{k_1}*\binom{n-k_1}{k_2} \neq \binom{n}{k_1 + k_2}$.

For example if you consider that in part 1) of your solution choosing math teachers $A,B,C,D$ and afterwards math teachers $E,F$ or first choosing math teachers $A,B,E,F$ and afterwards math teachers $C,D$ leads to the same committee. you see that you have double-counted those instances.

$\endgroup$
0
$\begingroup$

You can break it down as you had if you like (and in this case it seems like it may even be the more efficient approach)

Let us look at one of the specific cases in more detail:

  • $6$ mathematicians and $2$ physicists

Here, we should pick which six mathematicians there are in $\binom{15}{6}$ ways, and then which two physicists there are in $\binom{15}{2}$ ways. This gives a total of $\binom{15}{6}\cdot \binom{15}{2}$ possibilities in this case.

For some strange reason which I cannot understand you got a total of $\binom{14}{4}\binom{15}{2}\binom{11}{2}$ for this case... It appears as though you removed a person from the pool of mathematicians, chose four of these mathematicians to whom you gave a special golden hat and told them they were special, picked two physicists, then put the missing mathematician back into the pool, then picked two more mathematicians from this group to whom you gave dunce caps to make them feel bad about themselves.

In such a scenario, the outcome where a particular mathematician is wearing a golden hat is considered a different outcome than if the mathematician is wearing a dunce cap. This is regardless whether or not the people on the committee are otherwise the same.

In reality, we don't care whether a person was picked in the first step versus the third step... they are otherwise considered the same to us and this is the source of your overcounting.

If you remain unconvinced, consider the problem of if you have $15$ mathematicians, $15$ physicists, we want to pick thirty of them in such a way that we picked at least $4$ mathematicians and at least $2$ physicists. There is clearly only one possiblity: namely the one where we picked all thirty available people.


Final answer then:

$$\binom{15}{6}\binom{15}{2}+\binom{15}{5}\binom{15}{3}+\binom{15}{4}\binom{15}{4}$$

$\endgroup$
1
  • $\begingroup$ Given the OP's answers in the second and third cases, I suspect you are focusing on a typo in the first case. To my mind, the OP has fallen into the trap of distinguishing the required mathematicians and physicists from additional mathematicians and physicists. $\endgroup$ Oct 3, 2019 at 9:35
0
$\begingroup$

In a case like that

$${14 \choose 4} {15 \choose 2} {11 \choose 2}$$

we are overcounting the physics teachers among the $15$ and the $11$.

$\endgroup$
0
$\begingroup$

It is a good idea to split up the problem into three sub-problems. But the way you approach the sub-problems is wrong. Take case 1: ${15 \choose 4}{15 \choose 2}{11 \choose 2}$ is the number of possibilities of selecting 4 math teachers out of 15, 2 physicists out of 15 and 2 other people out of 11 people that are neither mathematicians nor physicists.

To compute the first sub-problem, you need to use ${15 \choose 6}{15 \choose 2}$. Can you take it from there?

$\endgroup$
0
$\begingroup$

You're double counting. For instance, suppose we label the math teachers $M_1$ through $M_{15}$. In the 6 mathematicians case, you're treating choosing $M_1$ as the "4" as different from choosing $M_1$ as one of the "2 remaining mathematicians from the 11 left". But there's no difference between those two cases. For the 6 mathematicians case, you should just have ${15 \choose 6} {15 \choose 2}$.

Consider a simpler case. How many ways are there to choose three people with from 2 math teachers and 2 physics teachers, if you need at least one of each? For the case where we end up with two math teachers, the logic you present would say "there are ${2 \choose 1}=2$ ways to pick which math teacher we're using to satisfy the 'at least one math teacher' requirement, and ${1 \choose 1}=1$ ways to choose a math teacher from the remaining 1 math teacher". But there's no difference between choosing one math teacher versus the other to be the "at least one".

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.