In how many ways can you divide the set of eight numbers $\{2,3,…,9\}$ into $4$ pairs such that no pair of numbers has g.c.d equal to $2$ ?
My solution goes like this:
First, we observe, that a pair can have gcd $d=2$ if both the numbers are even. It is easy to see that, any two even numbers paired up, has $d=2$ (We consider the gcd to be $d$), except the pair, $(4,8)$ which has $d=4.$ Now, the odd numbers in the given set are $\{3,5,7,9\}$ and the even numbers in the given set are $\{2,4,6,8\}.$ Now, if we choose any two odd numbers to form a pair, it is possible as all the conditions are satisfied. Now, the thing is, if we want to have all the pairs constituted of only odd numbers, now,this is absurd as, we have only $4$ odd numbers and the maximum possible pairs that can be made with them is $2.$ Now, if we have these maximum number of odd pairs,i.e $2$ odd pairs then, we have to build another two pairs with only the even numbers. This is where, the problem is, since, we can have $(4,8)$ as the only remaining choice and for the $4th$ pair, with the remaining even numbers, left, if we try to pair up, them, in any way we end up, with $d=2$ for the 4th pair. Thus, having $2$ odd pairs, is not feasible. Thus, we can have, atmost one odd pair. So now we have two cases: Case 1: There are no odd pairs in the 4 pairs and Case 2: One odd pair is there. In the former case, we can build the pairs, either with an odd and even number i.e $(odd,even)$ and we might take the pair $(4,8)$ as one of the 4 pairs. Here, we have, two subcases. Subcase 1: We have all the 4 pairs of the form $(odd,even).$ The number of ways, this can be done is: We first, choose an odd number and an even number and then continue the process with the remaining numbers i.e $\frac{\binom{4}{1}\binom{4}{1}\binom{3}{1}\binom{3}{1}\binom{2}{1}\binom{2}{1}\binom{1}{1}\binom{1}{1}}{4!}$ ways. Next, subcase is the case, when some pairs are of the form $(odd,even)$ and we have $(4,8)$ as one pair. Thus, we need to choose 3 pairs, of the form $(odd,even)$. This case is not possible as we won't have any even number left, to create the 4th pair. Now, this completes case 1.
For case 2, we have two subcases as well. Subcase 1: Out of the to be chosen 3 pairs, all are of the form $(odd,even)$ and Subcase 2: We have $(4,8)$ as one pair decided and the rest are of the form $(odd,even).$ Now, Subcase 1, is not possible, since, we dont have any odd number left to form 4th pair. As for subcase 2, we have to choose 2 pairs. This can be done in $\frac{\binom{2}{1}\binom{2}{1}\binom{1}{1}\binom{1}{1}}{2!}$ ways. Thus, the total number of ways is :$\frac{\binom{4}{1}\binom{4}{1}\binom{3}{1}\binom{3}{1}\binom{2}{1}\binom{2}{1}\binom{1}{1}\binom{1}{1}}{4!}$$+\frac{\binom{2}{1}\binom{2}{1}\binom{1}{1}\binom{1}{1}}{2!}.$
Is the above solution correct? If not, where is it going wrong? I know there might be thousands of posts concerning the same topic, but I just want to verify, whether this process is valid or not.
Best Answer
The $2$ must be paired with an odd number. The $6$ must be paired with an odd number different than that paired with the $2$. The remaining four numbers can be paired in any way... pick which number is paired with the smallest remaining number.
I get a total of $4\cdot 3\cdot 3 = 36$ total ways. Hardly any casework necessary.
With regards to your attempt, for your case where we have the pair $\{4,8\}$ that would be one (even,even) pair (which must have been the $\{4,8\}$ pair), one (odd, odd) pair, and two (even,odd) pairs, there should have been $4\cdot 3 = 12$ outcomes here, not just $2$. We choose what was paired with the $2$, and we choose what was paired with the $6$, and the remaining two odd numbers get paired together.
Alternatively, you pick the two odd numbers paired together in $\binom{4}{2}$ ways, and then you choose how to split the remaining numbers in two ways for $\binom{4}{2}\cdot 2 = 12$ ways. You seem to have skipped this step of choosing which odds were paired.