0
$\begingroup$

Consider the following question:

A committee of $4$ is to be chosen from $7$ people. $2$ of the $7$ people cannot work together. How many committees are possible if the two do not work together.

Here is how I am solving it

Total No. of possibilities = With Enemies + Without Enemies

Total No. of possibilities = $\tbinom{7}{4} = 35$

With Enemies (I considered the workers who are enemies as a single unit) = $\tbinom{6}{4} = 15$

Now I am getting $35-15 = 20$ which is wrong, I was suppose to get $25$. Could anyone tell me where I am going wrong ?

  • 1
    Think about the logic behind 6-choose-4. Are there really 6 items to choose from? Are you really choosing 4 items?2012-08-16

2 Answers 2

6

You went astray in counting the number of unacceptable committees. To form an unacceptable committee, you must first choose the two enemies and then fill out the rest of the committee with any $2$ of the remaining $5$ people, so there are $\binom52=10$ unacceptable committees. Your final result will then be $35-10=25$, which is correct.

You can also calculate the number of acceptable committees directly. There are $\binom54=5$ committees that can be formed without including either of enemies. If you include one of the enemies, there are $2$ ways to choose which one to include and then $\binom53$ ways to choose the other $3$ committee members, for a total of $\binom54+2\binom53=2\cdot10=5+20=25$ possible committees.

Added: When you group the enemies as one entity and then choose $4$ of the resulting $6$, you’re making two mistakes. First, those $\binom64=15$ foursomes include the $\binom54$ committees that can be chosen from the $5$ non-enemies. Secondly, if the enemy pair is one of the $4$ that you choose, you’re also choosing three more people, so you’re making a $5$-person committee.

  • 0
    @Gerry: I could, but with ‘Where did I go wrong?’ questions I prefer to err in the other direction and give either a fully explanation or at least a solid start to one as a detailed hint.2012-08-16
1

Suppose the seven people are A,B,C,D,E AND F and A and B are enemies. Ways in which acceptable communities can be formed are:

i. Including A and any 3 of the other 5 people, excluding B.

ii. Including B and any 3 of the other 5 people, excluding A.

iii. Excluding both A and B.

Number of ways in which i can be done = $\tbinom{5}{3}$ = 10

Number of ways in which ii can be done = $\tbinom{5}{3}$ = 10

Number of ways in which iii can be done = $\tbinom{5}{4}$ = 5

So, total possible ways = 25.