4. Combinations4.1. At an annual conference, each of five companies has sent two representatives. A four-member committee is to be formed from these ten representatives. What is the number of different committees that can be formed if two people from the same company cannot both serve on the committee?A. 16
B. 40
C. 80
D. 120
E. 160
Approach 1:Since the committee must not include both representatives from the same company, only one representative from each chosen company can be selected.
The number of ways to select four companies that will send one representative each to the committee is given by \(C^4_5\).
For each of these four companies, there are two choices for the representative. This gives \(2 * 2 * 2 * 2 = 2^4\) possibilities.
Therefore, the total number of ways to form the committee is \(C^4_5 * 2^4 = 5 * 16 = 80\).
Approach 2:• The first person on the committee can be any one of the 10.
• The second person can then be selected from only 8 people, since the first person and the other representative from that same company can no longer both be included together.
• The third person can then be selected from only 6 people, since the first two selected people and the other representatives from their companies are excluded.
• The fourth person can then be selected from only 4 people, since the first three selected people and the other representatives from their companies are excluded.
So, this gives 10 * 8 * 6 * 4 ordered groups.
However, this number includes ordered arrangements, meaning it includes all possible orderings of the same committee, such as (ABCD), (ABDC), (ADBC), ... which all represent the same four-member committee. Since 4 distinct people can be arranged in 4! ways, we should divide 10 * 8 * 6 * 4 by 4!.
Therefore, the number of combinations is:
\(\frac{10 * 8 * 6 * 4}{24} = \frac{1920}{24} = 80\)
To explain more clearly why we divide by 4!, consider a smaller example. Suppose there are two companies, each sending two representatives: \(A_1\), \(A_2\) and \(B_1\), \(B_2\). We want to choose a two-person committee such that both people are not from the same company. The possible committees are:
\(A_1, B_1\)
\(A_1, B_2\)
\(A_2, B_1\)
\(A_2, B_2\)
So only 4 such committees are possible.
But if we count in order, the first person can be chosen in 4 ways, and the second person can then be chosen in 2 ways. This gives 4 * 2 = 8. That count is too large because it includes duplicates. For example, choosing \(A_1\) first and then \(B_1\) gives the same committee as choosing \(B_1\) first and then \(A_1\). So each committee is counted \(2!\) times, and we divide by \(2!\):
\(\frac{8}{2!} = 4\)
The same idea is why, in the original question, we divide by \(4!\).
Answer: C
Takeaway:Most GMAT combinations questions are fairly straightforward and can often be solved in more than one way. It is useful to be comfortable with different approaches, because a second method can help you double-check your work if you are not fully confident in the first one. Also, in combinations questions, always pay attention to whether your method is counting ordered groups or unordered groups, and make sure that matches what the question is actually asking for.
What this question tests:This question tests basic combinatorics under a restriction. It also tests whether you can recognize two valid counting methods for the same problem: counting in stages, or counting permutations first and then converting to combinations.