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?
$\begingroup$
$\endgroup$
4
asked Dec 17, 2017 at 22:50
-
2$\begingroup$ Are they all different? $\endgroup$– Beastly GerbilCommented Dec 17, 2017 at 22:55
-
$\begingroup$ Not necessarily. $\endgroup$– Bernardo Recamán SantosCommented Dec 17, 2017 at 23:08
-
$\begingroup$ There is not a unique solution if the numbers are not necessarily all different. $\endgroup$– micsthepickCommented Dec 18, 2017 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$– TweakimpCommented Dec 18, 2017 at 5:55
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ The above solution is indeed the only solution, as verified by Freddy Barrera of Colombia Aprendiendo. $\endgroup$ Commented Dec 18, 2017 at 3:13
$\begingroup$
$\endgroup$
2
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$– votbearCommented Dec 18, 2017 at 3:06
-
$\begingroup$
$\endgroup$
1
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).
-
$\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$ Commented Nov 10, 2021 at 12:43