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?

  • $\begingroup$ I posted another case of this puzzle at: math.stackexchange.com/questions/2234076/…. $\endgroup$ Apr 16, 2017 at 13:36
  • $\begingroup$ "Exactly the same" in the sense "isomorphic"? $\endgroup$
    – Ankoganit
    Apr 16, 2017 at 13:49
  • $\begingroup$ Yes, @Ankoganit. $\endgroup$ Apr 16, 2017 at 13:52
  • $\begingroup$ By 'partition of 100' you mean, the sum of the integers equals 100, that is , are you referring to the definition from number theory? $\endgroup$
    – elias
    Apr 16, 2017 at 14:19
  • 1
    $\begingroup$ @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. $\endgroup$
    – xnor
    May 13, 2017 at 22:38

2 Answers 2


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.

enter image description here


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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.