Mr. Porter has 12 students in his combinatorics class. In the first week of class, he
tells his students to break up into 4 groups of 3 people each to work on a project.
In the second week, he assigns another project, and he tells his students to break
up into 6 groups of 2 people each, such that none of the people in each group were
in the same group in the first week. In how many ways can the students form the
groups in the second week? (Assume that the order in which they form the groups
does not matter.)
(A) 1296 (B) 2546 (C) 2995 (D) 3348 (E) 10395
First, I pick some random person named Joe. Then, he has 9 choices for who he can be paired up with. This step eliminates B and C. Now we pick another person from Joe's group. He has 8 people to choose from, but we need to divide by 2 for overcounting to get $9\cdot 8/2=36$. The final person has $7$ ways. But, none of the answers are multiples of $\text{lcm}(36,7)=252$.
Help?
Best Answer
WE Tutorial School's approach of looking at graphs with parallel edges is pretty neat and simple. Here is a more painstaking way that involves tons of casework, but has the virtue of completing OP's attempt.
Let Joe's original group of 3 be Joe, Alice, and Bob.
There are $9$ choices for Joe's new partner.
Alice has $8$ choices for her partner. There are two cases to consider.
Case 1. Alice's partner was in the same group of 3 as Joe's partner. ($2$ possibilities)
Case 2. Alice's partner was not in the same group of $3$ as Joe's partner. ($6$ possibilities)
We take each case separately.
Case 1: Bob now has $7$ choices.
One person is in the same group as Joe's partner and Alice's partner. If he chooses that person, then we just need to form pairs out of the remaining two untouched groups of $3$; there are $6$ ways to do that.
Otherwise, Bob chooses one of the $6$ people in the two untouched groups of $3$. Now there remains an untouched group of $3$, another group with $2$ people left, and another group with $1$ person left. There are $6$ ways to pair them up, since each pair must contain one person from the untouched group of $3$.
Case 2: Bob also has $7$ choices in this case. There is one untouched group of $3$, and two groups of two people each.
If Bob chooses someone from a group of $2$ ($4$ ways to do this), then there are again $6$ ways to pair up the remaining $6$ people.
If Bob chooses someone from the group of $3$ ($3$ ways to do this), then there are three groups of $2$ left. There are $8$ ways to pair them up.
Combining everything we have $$9 \cdot (2 \cdot (1 \cdot 6 + 6 \cdot 6) + 6 \cdot (4 \cdot 6 + 3 \cdot 8)) = 3348.$$