Committee Counting with Overlapping Restrictions
A B.Sc. CSIT club must send a five-member committee to a national hackathon from nine volunteers: five first-years (A, B, C, D, E) and four second-years (P, Q, R, S). The rules require at least two first-years and at least two second-years on the committee. Two additional constraints apply: A and P refuse to serve together, and B will serve only if C also serves. A student proposes this count: choose 2 first-years from 5, choose 2 second-years from 4, then choose the fifth member from the remaining 5 people, giving 10 × 6 × 5 = 300 committees. A second student says the answer should be obtained by subtracting invalid committees from the unrestricted total but gets confused about double counting. The adviser asks for a defensible count and a clear explanation of where the 300 calculation goes wrong.
1. Explain why 10 × 6 × 5 = 300 overcounts, using a concrete committee that is counted more than once.
Read the worked answer
The product 10 × 6 × 5 treats the committee as if it had a labeled "chosen pair" and a labeled "extra person." But a committee with 3 first-years and 2 second-years can be produced in three ways: choose any two of its three first-years as the initial pair and let the third be the fifth member. For example, the committee {A, C, D, Q, R} arises from initial first-year pairs AC (extra D), AD (extra C), and CD (extra A). The same happens for committees with 2 first-years and 3 second-years, which are counted three times. Committees with 2 first-years and 2 second-years do not occur because the fifth member necessarily makes one side size 3. Hence 300 is not a count of distinct committees.
2. Compute the number of valid committees. Show the counts of committees containing both A and P, committees containing B without C, and their overlap.
Read the worked answer
Unrestricted committees of size 5 with composition 2F+3S or 3F+2S: C(5,2)C(4,3)+C(5,3)C(4,2)=40+60=100. Count committees containing both A and P. For 2F+3S, A and P fill the first-year slots, so choose 3 of 4 second-years: 4. For 3F+2S, choose the third first-year from {B,C,D,E}; if it is B, B's condition requires C but no slot remains, so exclude B; choices C,D,E give 3, then choose 2 of 4 second-years: 3×6=18. Total 22. Count committees with B but without C. For 2F+3S: other first-year from {A,D,E}. If A, P must be excluded, leaving second-years Q,R,S, choose all 3: 1. If D or E: 2 choices, each with C(4,3)=4, giving 8; total 9. For 3F+2S: first-years include B and two of {A,D,E}. If A is included (2 pairs), P excluded, choose 2 of {Q,R,S}: 3 each, giving 6. If {D,E}, choose 2 of 4: 6. Total 12. B-without-C total 21. Overlap: A,P,B present, C absent, composition 3F+2S; choose 2 of 4 second-years: 6. Invalid union =22+21−6=37. Valid =100−37=63.
3. The adviser says the A/P rule is more costly than the B/C rule. Use your counts to evaluate that claim, noting overlap.
Read the worked answer
The claim is only slightly true. The A/P restriction alone rules out 22 committees from the unrestricted 100, while the B/C restriction alone rules out 21. However, 6 committees violate both restrictions. Therefore the number of committees lost uniquely to A/P is 22−6=16, and the number lost uniquely to B/C is 21−6=15. The total invalid set is 16+15+6=37. So A/P eliminates one more committee than B/C, but the two rules overlap substantially and neither is dramatically more costly. A count that simply added 22 and 21 would double-count the 6 overlap committees and give 43 invalid instead of 37.