9
$\begingroup$

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

$\endgroup$
4
  • 2
    $\begingroup$ Are they all different? $\endgroup$ Dec 17 '17 at 22:55
  • $\begingroup$ Not necessarily. $\endgroup$ Dec 17 '17 at 23:08
  • $\begingroup$ There is not a unique solution if the numbers are not necessarily all different. $\endgroup$ 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
10
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ The above solution is indeed the only solution, as verified by Freddy Barrera of Colombia Aprendiendo. $\endgroup$ Dec 18 '17 at 3:13
0
$\begingroup$

I now realise that both of these solutions are not valid

soln1

.

soln2

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.

$\endgroup$
2
  • $\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
-1
$\begingroup$

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:

  1. 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, ...

  2. 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.

  3. 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).

$\endgroup$
1
  • $\begingroup$ But nodes 1 and 6 are not connected, ergo they can't share a factor (and of course, they can't be the same number) $\endgroup$ Nov 10 '21 at 12:43

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.