Competition problem — Combinatorics

Library / /224 of 377

Combinatorics Difficulty 5.2 AIME, harder Prove it United States

Problem:
A committee of 5 is to be chosen from a group of 9 people. How many ways can it be chosen, if Bill and Karl must serve together or not at all, and Alice and Jane refuse to serve with each other?

Solution

Solution:
If Bill and Karl are on the committee, there are $\binom{7}{3} = 35$ ways for the other group members to be chosen. However, if Alice and Jane are on the committee with Bill and Karl, there are $\binom{5}{1} = 5$ ways for the last member to be chosen, yielding 5 unacceptable committees.

If Bill and Karl are not on the committee, there are $\binom{7}{5} = 21$ ways for the 5 members to be chosen, but again if Alice and Jane were to be on the committee, there would be $\binom{5}{3} = 10$ ways to choose the other three members, yielding 10 more unacceptable committees.

So, we obtain $(35 - 5) + (21 - 10) = 41$ ways the committee can be chosen.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.