7
$\begingroup$

Find six positive natural numbers, not necessarily distinct, whose sum is 1000 and which, 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).

Find the solutions in which the product of the six numbers is as small and large as possible.

enter image description here

Improve this question
$\endgroup$
8
  • $\begingroup$ what's an edge? how many does that graph contain? $\endgroup$
    – Jasen
    Commented Mar 29, 2018 at 20:02
  • $\begingroup$ @Jasen: Lines (in this case straight) joining circles, better known as vertices in graph theory terminology. $\endgroup$
    – Bernardo Recamán Santos
    Commented Mar 29, 2018 at 20:28
  • $\begingroup$ should I be seeing two or or five edges? some graph theory allows more than two nodes on an egde. $\endgroup$
    – Jasen
    Commented Mar 29, 2018 at 20:33
  • $\begingroup$ You rejected my (now deleted) answer with the reason that "vertices which have no edge between them have no common divisor, hence no more than two of them can be even." Where is that said exactly in your puzzle? If so, how would two numbers be equal ("not necessarily distinct")? Sorry if I'm missing something obvious to you, but I'm not used to mathematical jargon and I might not be alone. $\endgroup$
    – xhienne
    Commented Mar 29, 2018 at 20:43
  • $\begingroup$ Am I right to think that the three numbers in the top, left and right circles are interchangeable? They are all in degree 1 vertices and all connect to the central circle of the cross. $\endgroup$
    – nickgard
    Commented Mar 29, 2018 at 20:55

2 Answers 2

Reset to default
5
$\begingroup$

I wrote a program and it produced:

The products are:

$53,361,000$ and $20,091,608,390,700$.

Some general comments:

To get a small product we want one large number and lots of small numbers. Conversely, to get a large product we want all the numbers to be close to $1000/6=166.66\dots$ I used this to reduce the search space. Since it wasn't a full search it's always possible I missed better solutions.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Through computer search I can confirm @nickgard's results. The same minimum can be also achieved with $924,50,11,7,5,3$. $\endgroup$
    – Freddy Barrera
    Commented Mar 30, 2018 at 13:11
4
$\begingroup$

An observation is that since 1000 is even, then there must be an even number of odd numbers. There cannot be 6 even numbers since there will be some that do not share an edge even though they are co-prime. By extension: There is no place where three shapes share edges. So there are exactly 2 or 0 even numbers, the rest are odd. Similarily for other primes there must be 2 or fewer multiples of it in the problem. (other primes other than 2 can exist once). We can also observe that for each node, the number of edges represents the minimum number of unique primes in the prime factorization of the node. So if we take the middle piece, the lowest value it can possibly take is: 2*3*5*7 = 210. It must be a multiple of 2 otherwise it will bust. There are many values it can take otherwise by replacing one prime, or by multiplying by one of its own prime again, so 420, 630 are easily found, so is 2 * 3 * 5 * 11 = 330, and so on. So now is the point where we want to minify. Start with the center as 210, and each "prong" is 3, 5, 7 leaving 775 leftover. The one below the cross is 2*31 = 26 and 713. 713/31 = 23 so it fits the last condition. This should yield the minimum solution. Similar reasoning should be used for the maximum. EDIT: Woops I made the wrong assumption for minimization. SO the middle should still be 210, make the single edges 2, 3, 5. Leaving us 7*13 = 91 directly below, and 689 = 13 * 53 below that. 689 + 91 + 210 + 2 + 3 + 5 = 1000

Improve this answer
$\endgroup$
3
  • $\begingroup$ the questions says "not necessarily distict" but your argument seems to require them to be distinct. (as there is no place on the graph where two or more equal numbers could fit and be joined to a third number) $\endgroup$
    – Jasen
    Commented Mar 29, 2018 at 20:03
  • 1
    $\begingroup$ While they are not necessarily distinct, the only way two identical numbers can be in the solution is if they have a common edge, and no other edge. So the numbers must be distinct $\endgroup$
    – wolfram42
    Commented Mar 29, 2018 at 20:17
  • 1
    $\begingroup$ Yes I would say the phrase "not necessarily distinct" is a (minor) flaw in the question, not the answer. Since they are in fact necessarily distinct. $\endgroup$
    – theonetruepath
    Commented Mar 30, 2018 at 0:17

Not the answer you're looking for? Browse other questions tagged or ask your own question.