17
$\begingroup$

The sum of $9$ positive natural numbers, not necessarily distinct, is $100$. If placed appropriately on the vertices of the following graph, two of them will be joined by an edge if and only if they have a common divisor greater than $1$ (that is, they are not relatively prime).

graph

What, in non-decreasing order, are those $9$ numbers? The answer is unique.

Improve this question
$\endgroup$
5
  • $\begingroup$ non-decreasing = ascending $\endgroup$
    – Tas
    Commented Mar 26, 2018 at 23:52
  • 5
    $\begingroup$ @Tas Not sure 1 2 2 3 counts as ascending, but it's certainly non-decreasing. $\endgroup$
    – HolyBlackCat
    Commented Mar 27, 2018 at 0:01
  • $\begingroup$ Do you have a general way of proving uniqueness or it is by brute force check? $\endgroup$
    – Surb
    Commented Mar 27, 2018 at 12:33
  • $\begingroup$ @Surb: For the time being, efficient computer aided brute force. $\endgroup$
    – Bernardo Recamán Santos
    Commented Mar 27, 2018 at 12:59
  • $\begingroup$ I have posted another instance of this puzzle at math.stackexchange.com/questions/2710554/… $\endgroup$
    – Bernardo Recamán Santos
    Commented Mar 27, 2018 at 19:43

3 Answers 3

Reset to default
18
$\begingroup$

Here's one solution (not sure if it's unique):

enter image description here

How I found it: by following the logic used to answer this similar question.

Clearly there are three overlapping sets of completely connected subgraphs (the four leftmost circles, then the next foursquare, then the rightmost foursquare). I associated each of these with a prime, and tried a few different possibilities until I found one that worked. I.e. something of the following form:

p---pq---qr---r s
|\ /|\ /|\ /|
|/ \|/ \|/ \|
p---pq---qr---r

How I found this specific solution:

I realised that the lone number on the right must be coprime with all the others, and the sum of all the others will be even if I used the pattern I was using with the top and bottom rows being identical. Thus we want each number on the left to be odd. The smallest possibility is to use the primes $3,5,7$, and clearly $3$ should be in the middle to make the products as small as possible.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Please don't delete your answer as a dupe, as it has an explanation as well. $\endgroup$
    – Phylyp
    Commented Mar 26, 2018 at 16:38
  • $\begingroup$ Maybe I'm missing something, but isn't it another valid solution if you replace your 7s with 8s and the 21s with 20s? Likewise replacing the 5s with 4s and the 15s with 14s results in yet another solution. I'm just a little skeptical since the OP claimed that there would exist one unique answer... $\endgroup$
    – Christoph
    Commented Mar 27, 2018 at 9:21
  • 1
    $\begingroup$ @Christoph No, because then the lone 4 would have to be connected to the 8s and 20s. $\endgroup$
    – Rand al'Thor
    Commented Mar 27, 2018 at 10:03
  • $\begingroup$ Ahh, missed that. Thanks for the clarification! $\endgroup$
    – Christoph
    Commented Mar 27, 2018 at 14:20
10
$\begingroup$

Not sure if it is unique but I found the following solution

enter image description here

Improve this answer
$\endgroup$
1
  • $\begingroup$ Argh! The page didn't update to show me an answer had been posted before mine :-( $\endgroup$
    – Rand al'Thor
    Commented Mar 26, 2018 at 16:30
-1
$\begingroup$

A solution has already been posted, which suggests the below is wrong, but I'm not sure why.

Put 9's in all the nodes on the left and 28 on the right. So, 9,9,9,9,9,9,9,9,28.

As stated, the numbers on the left don't have to be distinct. The sum of 8*9 and 28 is 100. They are all positive natural numbers, and 28 has no common divisors with 9, while 9 of course has common divisors with itself.

What is wrong with this?

Improve this answer
$\endgroup$
2
  • $\begingroup$ All the nines have common divisors between them, but they are not connected to every single other nine in the graph. $\endgroup$
    – Joonas Ilmavirta
    Commented Mar 27, 2018 at 11:47
  • $\begingroup$ The question states that two "vertices will be joined by an edge if and only if they have a common divisor greater than 1." So if all the nodes on the left are 9s, they should all be connected to each other. $\endgroup$
    – Tobbs
    Commented Mar 27, 2018 at 12:12

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