Track / Stage 5 / 92 of 400 #1172 of 2444

Problem 1172

AIME late

Combinatorics Difficulty 5.2 Prove it Harvard-MIT Mathematics Tournament · United States

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?

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Official 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.

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