The sum of six positive integers is 200. If placed appropriately on the vertices of this graph, two of them will be joined by an edge if, and only if, they are not relatively prime, that is, if they have a common divisor greater than 1. What are those six integers?
Let's number the vertices to make it easier.
(1)----- / \ \ (2)---(3) (4)--(5) \ / / (6)-----
One possible answer is, in order,
21, 39, 39, 70, 5, 26
Based on the nature of this graph, we can deduce that the numbers connected by the lines all share a common denominator, which none of the other numbers has. This means any primes that make up this denominator will not make up any of the other numbers.
For example, if (1) and (4) is divisible by the prime number 2, none of the other numbers will be divisible by 2 (or else they must be connected to both (1) and (4))
From the shape of the graph, we can infer that:
(1), (2), (3) share a common denominator (let us call this A)
(2), (3), (6) share a denominator B
(1), (4) share a denominator C
(6), (4) share a denominator D
(4), (5) share a denominator E
This also means that (1) = AC, (2) = AB, (4) = CDE, and so on.
So basically, we are looking for 5 numbers A,B,C,D,E, all relative primes to each other, where:
AC + AB + AB + CDE + E + BD = 200.
Through trial and error, i have found a valid configuration (3, 13, 7, 2, 5). I did this by just trying different combinations of 5 prime numbers for A, B, C, D, E.
There may be more configurations, and my brute force method may not work if the total was larger - i assumed that every letter is a prime number, while it is possible that any of the letters are a combination of more than one prime.
However, with 200 as the total limit, this is highly unlikely. Having any of the letters be a combination of multiple primes means that we will need more than 5 primes, which will result in larger numbers. Even using the smallest 5 primes i was already barely fitting in the total limit, so i quickly scratched this possibility.
I now realise that both of these solutions are not valid
How I found out:
The clue is by finding groups which share no common factor. By doing this we find that there are a minimum of four coprime factors in the entire puzzle. By searching through the first 8 primes I found these answers. There could be more solutions by accounting for larger primes or other combination of not-prime-but-coprime numbers.
One particular solution, if label the nodes in the order of left to right, top to bottom:
1:42, 2:32, 3:32, 4:39, 5:13, 6:42
The logic is as follows:
The easiest common divisor is 2 and 3
1.1 Make 1, 2, 3, 6 share the common divisor 2; 1, 4, 6 share the common divisor 3.
1.2 Make 4, 5 share a common divisor which is an odd prime number, e.g. 5, 7, 11, 13, ...
Now we see that 1, 6 are multiples of 6; we further make 2, 3 power of 2. We can set 1==6, 2==3 for simplicity.
The reason why 1, 2, 3, 6 share the common divisor 2 instead of 3 is to ensure that the sum of these 6 numbers is even (which is 200).