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.
Final Short Answer:
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
$(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$
Well, thanks the hint from question owner, I now tried out with the form $2^x3^y$:
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$
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:
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:
Now the minimum is reduced again & again to $2^43^25^1 = 720$
I hope it's the optimal minimum :(
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
While the total product of each line is
The diagram of n’s [The lines are somehow missing
The Excel of conversion: