# A mystery partition of 100

Given a multiset (a set with repeated elements allowed) of positive integers, its P-graph is the loopless graph whose vertex set consists of those integers, any two of which are joined by an edge if they have a common divisor greater than 1, that is, they are not relatively prime.

The P-graph of a certain mystery partition of 100 has 10 vertices and 35 edges. I've been told that no other partition of 100 has exactly the same P-graph. What is this mystery partition of 100?

• I posted another case of this puzzle at: math.stackexchange.com/questions/2234076/…. Commented Apr 16, 2017 at 13:36
• "Exactly the same" in the sense "isomorphic"? Commented Apr 16, 2017 at 13:49
• Yes, @Ankoganit. Commented Apr 16, 2017 at 13:52
• By 'partition of 100' you mean, the sum of the integers equals 100, that is , are you referring to the definition from number theory? Commented Apr 16, 2017 at 14:19
• @BernardoRecamánSantos Is there a nice clever way to get the answer, or to show it's right? If it requires a bunch of casework, I'd rather not go throughthat.
– xnor
Commented May 13, 2017 at 22:38

Found by extensive computer search, the partition in question is $2,4,4,6,10,10,14,14,15,21$. The P-graph of this partition has exactly 35 edges. The computer search verified that no other partition of 100 has precisely this P-graph.

This is the P-graph of the partition and its complement.

My approach is a parity observation, and is helped by the fact that it is a multiset. Otherwise it would be a bit time consuming.

So, among 10 numbers, there can be ${10 \choose 2}=45$ pairs, that is, $45$ edges and there are only 35 edges, so that means we can find $10$ pairs only that have gcd $1$.

Now, if we let one of the numbers be $1$, then already $9$ edges go off from $45$, since gcd$(a,1)=1$ for any $a \in \mathbb{Z}$.

We need to let only one edge go off.

So among the remaining $9$ numbers that add up to $99$ we need to have two numbers that are relatively prime themselves, but not to the other numbers.

Since them sum is odd, there should be an odd number of odd numbers, so we simply take one odd number and a power of two (these two will have gcd 1) and try to make all the other numbers have both $2$ and some factor of this odd number in them.

A very intuitive construction is the following $\big\{4,10,10,10,10,10,10,10,25\big\}$. Here, only the pair $(25,4)$ has gcd $1$, and all the other pairs have either a $5$ or a $2$ common in them.

Check that $\big\{1,4,10,10,10,10,10,10,10,25\big\}$ is indeed a partition satisfying the given criterion.

• No. There is at least one other partition of 100 into 10 parts whose P-graph is the same. Commented Apr 17, 2017 at 20:44
• a partition with a P-graph which is isomorphic with this one is {5,6,6,6,6,6,6,6,9,44} Commented Apr 18, 2017 at 6:29