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
    You stated **"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 $_5C_2$ unacceptable committees."** Could you explain this a bit more I still don't get it. How did you get 5 and how did you get 2 ?2012-08-16
  • 0
    Another hint trampled by an answer.2012-08-16
  • 0
    Misty, how did *you* get 6, and how did *you* get 4?2012-08-16
  • 0
    @GerryMyerson To get 6 , I grouped the two enemies as one so 7-1 = 6 and 4 was the committee requirement.2012-08-16
  • 1
    @Misty: After you’ve put the two enemies on your committee (which is the only way to make it unacceptable), you still need $2$ more members. There are $7-2=5$ people left who aren’t yet on your committee, so you must choose $2$ of these $5$. You can do this in $\binom52$ ways.2012-08-16
  • 0
    @Gerry: I can’t honor a hint that I’d not seen when I wrote and posted my answer.2012-08-16
  • 0
    @Brian M. Scott good solution.2012-08-16
  • 0
    @BrianM.Scott Thanks for clearing that up2012-08-16
  • 0
    @Misty: You’re welcome. I’ve also added an explanation of why amalgamating the enemies doesn’t work quite the way you wanted it to work.2012-08-16
  • 0
    True, Brian, but what you could do is post a hint yourself, instead of an answer. I'm not saying you should have, only that you could have.2012-08-16
  • 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.