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$ – Bernardo Recamán Santos Apr 16 '17 at 13:36
  • $\begingroup$ "Exactly the same" in the sense "isomorphic"? $\endgroup$ – Ankoganit Apr 16 '17 at 13:49
  • $\begingroup$ Yes, @Ankoganit. $\endgroup$ – Bernardo Recamán Santos Apr 16 '17 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 '17 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 '17 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.

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$ – Bernardo Recamán Santos Apr 17 '17 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 '17 at 6:29

Your Answer

