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

  • 2
    $\begingroup$ Are they all different? $\endgroup$ – Beastly Gerbil Dec 17 '17 at 22:55
  • $\begingroup$ Not necessarily. $\endgroup$ – Bernardo Recamán Santos Dec 17 '17 at 23:08
  • $\begingroup$ There is not a unique solution if the numbers are not necessarily all different. $\endgroup$ – micsthepick Dec 18 '17 at 1:09
  • $\begingroup$ @micsthepick why? If your solution is of form a, a, b,b, c, d, switching the as or bs gives the same, unique solution. $\endgroup$ – Tweakimp Dec 18 '17 at 5:55

Let's number the vertices to make it easier.

  /   \    \
(2)---(3)  (4)--(5)   
  \   /    /

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.

  • $\begingroup$ The above solution is indeed the only solution, as verified by Freddy Barrera of Colombia Aprendiendo. $\endgroup$ – Bernardo Recamán Santos Dec 18 '17 at 3:13

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.

  • $\begingroup$ Dang, you beat me by a few mins :P $\endgroup$ – votbear Dec 18 '17 at 3:06
  • $\begingroup$ I messed up the solution though :P $\endgroup$ – Jay Dec 18 '17 at 3:07

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.