16
$\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.

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

$\endgroup$
  • $\begingroup$ Please don't delete your answer as a dupe, as it has an explanation as well. $\endgroup$ – Phylyp Mar 26 '18 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 Mar 27 '18 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 Mar 27 '18 at 10:03
  • $\begingroup$ Ahh, missed that. Thanks for the clarification! $\endgroup$ – Christoph Mar 27 '18 at 14:20
10
$\begingroup$

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

enter image description here

$\endgroup$
  • $\begingroup$ Argh! The page didn't update to show me an answer had been posted before mine :-( $\endgroup$ – Rand al'Thor Mar 26 '18 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?

$\endgroup$
  • $\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 Mar 27 '18 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$ – Ben J Mar 27 '18 at 12:12

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.