# IMO combinatorics partitioning prime number products from 1973 shortlist

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?

Observations:

There are $$\binom{7}{2}$$ possible product pairings consisting of distinct primes from $$P$$, and then also 7 prime squares, so together that accounts for the 28 elements in $$C$$.

Now suppose $$p^2$$ and $$q^2$$ were in the same partition. Then the condition would require that the other 2 numbers in the partition both be $$pq$$, which is impossible because $$C$$ contains exactly 28 elements meaning that $$C$$ contains each product pairing (as formed in the ways discussed above) exactly once.

So each of the partitions must contain a unique square, $$a$$ (say), and must take one of the forms {$$a^2, ab, ac, ad$$} or {$$a^2, ab, ac, bc$$}.

It remains to count the possible ways of pairing the remaining elements in these forms for each of the seven sets.

The IMO compendium solution arrives directly to this point before stating:

It is now easy to count up the partitions

There is a thread from half a decade back on this question but it wasn't solved and got messy.

Some tentative thoughts:

For the form {$$a^2, ab, ac, bc$$}, the problem reduces to the number of bijections of the set

{$$1,1,2,2,3,3,4,4,5,5,6,6,7,7$$}

to

{$$n_{1a}, n_{1b}, n_{2a}, n_{2b}, ... n_{7a}, n_{7b}$$}

such that $$n_i\neq i$$ and $$n_{ia}\neq n_{ib} \ \forall i$$ for which the derangement formula (permutations without fixed points) might be a start, though I'm not convinced this is a step forwards.

I suspect PIE would work somehow.

• I tried to think about partitioning the complete graph on 7 vertices (the primes) into 3-edge sets, and adding one loop on each vertex (the squares). But I haven't really seen anything clever that makes this counting easy either. Jul 4, 2022 at 21:45

Arthur's suggestion above is a great starting point. For simplicity I'll label the $$7$$ vertices ABCDEFG. The {AA, AB, AC, BC} case is essentially covering the graph with $$7$$ triangles (of seven colors), each using $$3$$ edges.

There are $$\binom{7}{3}=35$$ possible triangles. Each vertex must be contained in $$3$$ of the ones we choose. So to count the permutations: pick a vertex and choose $$3$$ of the triangles containing it. WLOG choose A, and make our first triangle ABC. $$15$$ of the $$35$$ triangles contain A; however, having chosen ABC, the $$8$$ choices containing a B or a C become impossible, leaving just $$15-1-8=6$$ choices.

Once we make a second choice (say, ADE), the third triangle containing A is forced: it must be AFG. So there are $$15 \times 6/6 =15$$ possibilities here. ($$/6$$ because we could have chosen in any order.)

Now we must choose $$2$$ more triangles containing, well let's keep it simple and choose B. There are fewer triangle choices remaining than you might think! B has already paired with A and C. But also, DE and FG have been paired together, so our fourth triangle can't contain those pairs. The remaining choices (containing B) are: BDF, BDG, BEF, BEG. And once we've picked one, the fifth choice is forced. We'll choose BDF and BEG for now. That's $$4/2=2$$ actual choices after removing order.

We need $$2$$ more triangles. Our choices are now pretty narrow: CDG and CEF. So narrow, in fact, that we'll use both; they're forced choices. That means that we should have $$15 \times 2 = 30$$ possible sets of triangles that cover the full graph. Each triangle is used in $$30 \times 7/35=6$$ of the sets.

Now, we could have started with another vertex. But do we now multiply by $$7$$? No. The $$30$$ possible sets of choices contain the rotations. Consider permuting our choices here forward by one (or rotating by one vertex, keeping the coloring), giving {BCD, BEF, BGA, CEG, CFA, DEA, DFG}. But if we rewrite those, we have {ABG, ACF, ADE, BCD, BEF, CEG, DFG}, which would have been found using the procedure starting from A. We need simply switch the colors around, since each actual color doesn't matter, so long as we have $$7$$ of them.

Oh... but wait. What of the squares? We have to color the loops. We'll say vertex A has color $$a$$, but note that vertex N need not have color $$n$$.

Each vertex has three colors to choose among, from the three triangles it's in. Well, the first one (A) does; color it $$a$$. B must be in a triangle with A, so it must choose one of the other two triangles, and it might as well take color $$b$$.

C is either in a triangle ABC, or not. In the first case, it has just one choice of color, $$c$$. Otherwise, it has... one choice. It must take the color of the triangle it's in with neither A nor B. D has the same lack of choice, as do the remaining vertices. That's $$6$$ choices for the $$7$$ vertices, but they're linked. We multiply $$30$$ by that to get $$180$$ possible colorings.

The {AA, AB, AC, AD} case is a bit different. Instead of single-color triangles, our figures are fanned out. We can think of the same graph, but rather than triangles, each vertex has three "outgoing" and three "incoming" segments. (These aren't actually directed; it's just a way of thinking of them.) Or, if you wish, each vertex will have $$3$$ segments of one color, and the other segments will each be a different color.

Let's go ahead and use our example case as our first choice. Starting from A, there are $$\binom{6}{3}=20$$ choices for our "outgoing" segments. We'll note this as A:BCD.

We'll move to B. This time, none of our three outgoing segments can go to A. That means we only have $$\binom{5}{3}=10$$ choices left over. For the example, it turns out that B:CDE is a safe choice-- in fact we can go around the graph coloring the three segments to the next three vertices $$7$$ times. But what about our next choice?

Well, if we start from C, we only have $$4$$ choices left. But if we skip to F, we actually have $$6$$ segments left to color. Oh dear; it looks like our choices are less independent and order will matter more here. Let's step back.

After picking A:BCD, we can go to E, which has no connections yet. We can even choose E:BCD if we like, leaving F and G still unmoored! Right? Maybe... wait a sec.

When we picked $$3$$ outgoing segments from A, we also forced the origins of the incoming segments. So E must have one outgoing segments that points to A. OK, but its other $$2$$ outgoing segments have $$5$$ points to pick from, or $$\binom{5}{2}=10$$... Oh. That's the same number. Huh.

Basically, the second vertex we pick is either forbidden from point to the first vertex, or required to point to it. It's the same situation!

The third vertex we pick has $$2$$ vertices it can't choose, or $$2$$ it must choose, or one of each. Respectively, it either has $$1$$ segment to choose among $$4$$, or $$3$$ to choose among $$4$$, or, interesting, a divergence? It can send two outgoing segments to $$4$$ choices. $$6$$ total choices for that situation.

Pokes head in Oh, hey. I never finished this, but neither did anyone else, so let's see if I can't take care of that.

If we step back a moment, we can see that our first two vertices can be chosen such that each of the five remaining vertices has one incoming and one outgoing segment. Consider starting with A:BCD. Now B, C, and D have one incoming segment defined, and E, F, and G have one outgoing segment defined. We pick any of B, C, or D as K, and use K:EFG.

Now each remaining vertex has one incoming and one outgoing segment, so we can safely say the third vertex will have $$6$$ possibilities.

The fourth vertex has three possibilities, no matter what; either it needs to send one segment to one of three vertices, or two to send, and $$\binom{3}{1}=\binom{3}{2}$$. Surprisingly, the fifth vertex still has a choice between the other two remaining vertices. The last choice has only one segment.

In total, then, we have $$20 \cdot 10 \cdot 6 \cdot 3 \cdot 2 =7200$$ different possibilities... before counting for order. We made five choices, meaning $$7200/120=600$$ total possibilities. (Note that the loops for squares have no choices; they must keep their own color.)

Now, I'll admit here that combinatorics is not my strongest suit. It's possible, even likely, that I've missed something subtle. I welcome corrections or thoughts.