
3. In how many ways can you partition the set $\{1,2, \ldots, 12\}$ into six mutually disjoint two-element sets in such a way that the two elements in any set are coprime?

(Martin Panák)


Solution. No two even numbers can be in the same set (pair). Let us call partitions of $\{1,2, \ldots, 12\}$ with this property, that is one even and one odd number in each pair, even-odd partitions. The only further limitations are, that 6 nor 12 cannot be paired with 3 or 9 , and 10 cannot be paired with 5 .

That means, that odd numbers 1,7 and 11 can be paired with numbers $2,4,6$, 8, 10, 12, numbers 3 and 9 with 2, 4, 8, 10 and number 5 can be paired with 2, 4, 6, 8,12 . We cannot use the product rule directly, we distinguish two cases: 5 is paired with 6 or 12 , in the second one 5 is paired with one of 2,4 , and 8 . The possible pairings are $2 \cdot 4 \cdot 3 \cdot 3 \cdot 2 \cdot 1=144$ in the first case, $3 \cdot 3 \cdot 2 \cdot 3 \cdot 2 \cdot 1=108$ in the second case. Together $144+108=252$ pairings.
