10
$\begingroup$

Place 19 different positive integers on the vertices of this graph so that the 13 products of three numbers in a straight line are all equal. Do so in such a way that the product is as small as possible.

enter image description here

$\endgroup$
  • $\begingroup$ There are several '3-in-a-row' in your diagram, e.g. top-middle, middle, bottom-middle. Do these count, or must they be on an actual line? $\endgroup$ – JMP Aug 26 at 4:14
  • $\begingroup$ @JonMarkPerry The 13 products on actual lines. $\endgroup$ – Bernardo Recamán Santos Aug 26 at 12:03
  • $\begingroup$ Well, you could add a few then. OK's answer gives (4,7,10), (11, 7,3) and (14,7,0) as at least three more answers! (I suppose this messes with minimality though). $\endgroup$ – JMP Aug 26 at 12:05
  • $\begingroup$ @JonMarkPerry Yes, it would mess the minimum by a lot! $\endgroup$ – Bernardo Recamán Santos Aug 26 at 13:46
12
+50
$\begingroup$

Final Short Answer:

enter image description here
Product = $720$

Derivation Process:

By observation, this graph is composed with many triangles, so that maybe "3" is the key to identify the "dimension" or "vector" concept.

By unique factorization theorem, every positive integer can be represented as the product of prime numbers and this representation is unique.

Based on above 2 reasons, I tried to solve this question with the form $a^x b^y c^z$. And by the theorem, every unique tuple $(x,y,z)$ ensures that $a^x b^y c^z$ is also unique.

Thus for base $a,b,c$, I picked the smallest primes $2,3,5$. Then we need at least 19 different integers to fill in the vertex, so I began to try $x=y=z=2$ due to there are 27 unique integer candidates vary from $2^03^05^0$ to $2^23^25^2$, but not working.

Then I tried with $x=y=z=3$, and it works :P

enter image description here

$(x,y,z)$ denotes the integer $2^x3^y5^z$, ex: $(1,1,2) \to 2^13^15^2 = 150$
The tuple/vector summation for all lines are $(3,3,3)$, hence the product is $2^33^35^3 = 27,000$

Improved:

Well, thanks the hint from question owner, I now tried out with the form $2^x3^y$:

enter image description here

Since the graph is line-symmetry, so that vertex which are on the center line should have $x=y$ property, and the rest should be symmetric, forming the property $(x,y) \to (y,x)$, from left to right.

Thus now the minimum product is reduced to $2^53^5 = 7,776$

Improved again:

This time I abandoned the symmetry approach due to some lower vector $(0,0)$ and $(1,1)$ are not used, $(x,y)$ need to be more "compact" when fill in the vertex.

Thus I attempted to put some lowers like $(0,1)$ or $(1,0)$ in joint vertex and put some highers like $(4,3)$ or $(3,4)$ in side vertex, and worked out:

enter image description here

Now the minimum is reduced again to $2^43^4 = 1,296$
I hope it is the final optimal answer and worth at least 30 upvotes :P

Improved again & again:

Need to reduce once more. Based on the upper limit $2^43^4 = 1,296$, I've listed all possibilities for the minimum which product is lower than $1,296$ and integer candidates are at least 20(due to we need 19 different integers to fill in):

  • $2^23^25^17^1 = 1,260 (36)$
  • $2^73^2 = 1,152 (24)$
  • $2^33^35^1 = 1,080 (32)$
  • $2^23^25^2 = 900 (27)$
  • $2^53^3 = 864 (24)$
  • $2^43^25^1 = 720 (30)$
  • $2^63^2 = 576 (21)$
  • $2^43^3 = 432 (20)$
  • $2^23^15^17^1 = 420 (24)$
  • $2^33^25^1 = 360 (24)$

And begin try and error process, finally worked out one:

enter image description here

Now the minimum is reduced again & again to $2^43^25^1 = 720$
I hope it's the optimal minimum :(

$\endgroup$
  • $\begingroup$ Nice, but not the minimum known to me. $\endgroup$ – Bernardo Recamán Santos Aug 26 at 15:04
  • 1
    $\begingroup$ Not far, and uses precisely the ideas you are trying. $\endgroup$ – Bernardo Recamán Santos Aug 26 at 15:17
  • 1
    $\begingroup$ @Conifers Nearly there! $\endgroup$ – Bernardo Recamán Santos Aug 26 at 16:54
  • 1
    $\begingroup$ @BernardoRecamánSantos I got some idea, wait me for a while :P $\endgroup$ – Conifers Aug 27 at 8:20
  • 1
    $\begingroup$ @Conifers No, I don´t know of any straightforward way of finding the minimum. In fact, I was surprised (and shocked!) to see you had lowered the minimum I had in mind (1080). I start from abundant numbers and construct plausible magic graphs using their many divisors. I don´t really know how to go backwards efficiently other then by pondered trial and error. $\endgroup$ – Bernardo Recamán Santos Aug 30 at 2:16
4
$\begingroup$

Inspired by another answer in another similar genre of question (forgot which one but I think the answer is by @Deusovi), this problem can be simplified to addition and then changing each number n in the circle to $4^n$ to achieve the task. Apparently this isn’t the optimal one, because the total product of all the numbers is

341704645

While the total product of each line is

$4^{13}$

The diagram of n’s [The lines are somehow missing :(]:

enter image description here

The Excel of conversion:

enter image description here

$\endgroup$
  • $\begingroup$ Can I see 8, 7.5, 4.5 (=20)? (right side) $\endgroup$ – JMP Aug 26 at 7:53
  • $\begingroup$ @Jon should be 8.5 instead of 7.5, will update later, thanks! $\endgroup$ – Omega Krypton Aug 26 at 7:56

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.