# Looking for another partition of 100

The sum of ten, not necessarily different, positive integers is 100. If placed adequately on the vertices of this graph, two of them will be joined by a line if, and only if, they have a common divisor greater than 1 (i.e. they are not relatively prime).

What are those ten integers?

Start by labeling as follows:

Solution process:

The only pairs of integers that could possibly be equal are $U$ and $X$, and $W$ and $Z$. This is because if two integers are equal to each other then they're certainly relatively prime to the same integers. Thus, for example, $Q \ne R$ because $R$ and $Y$ are not relatively prime but $Q$ and $Y$ are.

Unfortunately we can't automatically deduce that $U = X$ or $W = Z$. It may be possible that, without loss of generality, $U = X^k$ for some integer $k$, with a similar possible relationship between $W$ and $Z$.

Because $U$ and $X$ are only joined to each other, I suspect that each has only one prime factor (that is, each is some power of the same prime). Theoretically it's possible that, say, $U = pq$ for two distinct primes $p$ and $q$, but then no other vertex aside from $X$ can have $p$ or $q$ as a factor, and that seems very limiting since we're trying to sum to $100$.

I started by building systematically and had to adjust as I went along. My graph theory and number theory skills are rusty so if there's a more systematic way that doesn't involve guess-and-check, I don't know what it is.

First, $S,T,Y$ are all adjacent to each other (adjacent = "joined by an edge" in graph theory terms [edge = "line segment" in graph theory terms]), so $S,T,Y$ must have at least one prime factor in common. This common factor is $3$.

Since $S$ is adjacent to $V$, and $T$ and $Y$ are not, then $S$ must have a prime factor that $T$ and $Y$ do not. This factor is $7$.

Also, $Y$ is adjacent to $R$, while $S$ and $T$ are not. Thus $Y$ must have a prime factor that $S$ and $T$ do not. This factor is $2$.

$R$ must have another prime factor that no other vertex has yet, since $R$ is adjacent to $Q$ and no other vertex is adjacent to $Q$. This factor is $5$.

If we assume the simplest case, i.e., no powers of primes and just the primes themselves, then we have $Q = 5, R = 10, S = 21, T = 3, V = 7, Y = 6.$

Thus the total sum so far is $5+10+21+3+7+6 = 52$. This means we need $U+X+W+Z = 48$. What luck! $48 = 22 + 26 = 11 + 11 + 13 + 13$. Take $U = X = 13$ and $W = Z = 11$ and we get one possible answer:

• The answer is unique. May 18, 2017 at 12:18
• @BernardoRecamánSantos, up to isomorphism. :P $\quad$
– user33097
May 18, 2017 at 12:25
• The partition of 100 is unique. No other partition of 100 has the same graph. May 18, 2017 at 13:54
• @BernardoRecamánSantos, I know, I was thinking isomorphism because the $11$s and $13$s could be swapped, thereby having different labels. But I forgot that (a) I provided the labels and (b) they're irrelevant anyway since a graph is just vertices and edges.
– user33097
May 18, 2017 at 13:59

If I understand correctly, there should be many solutions to this. Then again, English is not my native language. Clockwise, starting from the topmost left: 26, 16, 8, 8, 10, 10, 10, 2, 8, 2.

I assume that I am wrong since this seems very easy, so please do correct me and explain if I haven't understood.

• I think that's not right because $26$ and $8$ aren't joined by an edge, which, according to the rules, means they shouldn't have any common factors greater than $1$. But they do ($2$).
– user33097
May 17, 2017 at 13:11
• Ah! Correct, they should be joined. This is what I have overlooked, that lines should not be static! I was approaching the graph in an incorrect way. Thank you! Please downvote and flag this answer. :) May 17, 2017 at 13:12
• You can always delete your own answer if you want... May 17, 2017 at 13:14
• Meh, I largely find downvoting to be petty and almost never do it. Also, what Mithrandir said.
– user33097
May 17, 2017 at 13:17
• But I'll flag so I can get progress towards a badge I'll never earn. :P $\quad$
– user33097
May 17, 2017 at 13:18