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

$\endgroup$
  • $\begingroup$ what's an edge? how many does that graph contain? $\endgroup$ – Jasen Mar 29 '18 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 Mar 29 '18 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 Mar 29 '18 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 Mar 29 '18 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 Mar 29 '18 at 20:55
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.

$\endgroup$
  • 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 Mar 30 '18 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

$\endgroup$
  • $\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 Mar 29 '18 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 Mar 29 '18 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 Mar 30 '18 at 0:17

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.