Let $P$ be a set of $7$ different prime numbers and $C$ a set of $28$ different composite numbers each of which is a product of two (not necessarily different) numbers from $P$. The set $C$ is divided into $7$ disjoint four-element subsets such that each of the numbers in one set has a common prime divisor with at least two other numbers in that set. How many such partitions of $C$ are there?
Book's solution:
I get how the subsets must either be $\{a^2,ab,ac,ad\}$ or $\{a^2,ab,ac,bc\}$, but how do we use this to count the number of partitions? I was thinking of proving it using a specific example such as $P = \{2,3,5,7,11,13,17\}$ and then generalizing it is the same thing.
I'm going to type up a partial answer with a view to completing it later... possibly with help!
In every partition the seven 4-sets always include one of the elements $a^2, b^2, c^2, d^2, e^2, f^2, g^2$ each; so those can be considered forced.
I'll enumerate first, the first type of 4-set:
Starting with the 2nd element of $a^2$, $a$ is now forced so there are 6 ways of choosing $b$ in $ab$. There are $5$ was of choosing $c$ in $ac$ and $4$ ways of choosing $d$ in $ad$.
Next we repeat for the $b^2$ set; again there are $6\times 5\times 4$ ways of choosing the free elements.
Continuing for all 7 4-sets gives us a total of $120^7$ solutions using only the first type of 4-set.
Repeating for the 2nd type of 4-set gives us $30^7$ solutions using only the 2nd type of 4-set, since in these 4-sets the 4th element $bc$ is forced as $b$ and $c$ are already chosen.
What remains now, is to enumerate which of the $3600^7$ combinations of these two types of 4-sets are disjoint. Clearly every combination must satisfy the "one perfect square per set" rule but I'm just scratching my head at the moment over whether this rule will be sufficient to guarantee they are all disjoint.