9
$\begingroup$

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). enter image description here

What are those ten integers?

$\endgroup$
7
$\begingroup$

Start by labeling as follows:

enter image description here

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:

enter image description here

$\endgroup$
  • $\begingroup$ The answer is unique. $\endgroup$ – Bernardo Recamán Santos May 18 '17 at 12:18
  • $\begingroup$ @BernardoRecamánSantos, up to isomorphism. :P $\quad$ $\endgroup$ – tilper May 18 '17 at 12:25
  • $\begingroup$ The partition of 100 is unique. No other partition of 100 has the same graph. $\endgroup$ – Bernardo Recamán Santos May 18 '17 at 13:54
  • $\begingroup$ @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. $\endgroup$ – tilper May 18 '17 at 13:59
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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$). $\endgroup$ – tilper May 17 '17 at 13:11
  • $\begingroup$ 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. :) $\endgroup$ – BadMathMan May 17 '17 at 13:12
  • 3
    $\begingroup$ You can always delete your own answer if you want... $\endgroup$ – user58 May 17 '17 at 13:14
  • 1
    $\begingroup$ Meh, I largely find downvoting to be petty and almost never do it. Also, what Mithrandir said. $\endgroup$ – tilper May 17 '17 at 13:17
  • $\begingroup$ But I'll flag so I can get progress towards a badge I'll never earn. :P $\quad$ $\endgroup$ – tilper May 17 '17 at 13:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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