IMO 1973 SL 4

Let P be a set of 7 different prime numbers and C a set of

imoshortlistmathematicsolympiad

IMO 1973 SL 4

Origin: GBR

Problem

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 com- mon prime divisor with at least two other numbers in that set. How many such partitions of C are there?

Solution

Each of the subsets must be of the form {a2, ab, ac, ad} or {a2, ab, ac, bc}. It is now easy to count up the partitions. The result is 26460.