Place 21 different positive integers on the vertices of this star so that the products of the three numbers in any of the 14 straight lines are all equal.
How small can the largest of the numbers be?
$\begingroup$
$\endgroup$
4
asked Apr 15 at 21:55
-
2$\begingroup$ Does the last sentence mean this is an [optimization] problem? $\endgroup$– bobbleApr 15 at 21:57
-
4$\begingroup$ Rollback: If you want to ask the question about equal sums, ask it as a separate question. $\endgroup$– Daniel MathiasApr 16 at 13:22
-
2$\begingroup$ Rollback: please don't change the goal of a puzzle after someone has already solved it. $\endgroup$– bobbleApr 16 at 14:23
-
1$\begingroup$ For the question of equal sums, there are many optimal solutions. Five of them even include the 3x3 diagonals. $\endgroup$– Daniel MathiasApr 16 at 21:12
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
After too much time trying to construct a better solution than loopy walt's excellent find, either by reducing a factor of 2 or eliminating the factor of 7, I gave it up and started coding. I was surprised by the result.
For anyone wanting to solve this theirself, the product is
$2^5\times 3^2\times 5$
and the largest number is
$60$
If you just want to see the singular* optimal solution my program found...
*Note: mintmocha has found another optimal solution. I missed it and a third solution because I initially limited the size of the product. A complete search fins a total of 5809 distinct solutions in numbers less than 100 and more than half a million in numbers less than 150.
The third optimal solution has a product of 10,080 and looks like this:
56 30 3 6 28 60 40 7 42 35 36 8 24 5 20 48 10 21 14 32 15
answered Apr 16 at 21:02
$\begingroup$
$\endgroup$
1
I think I got it down to
140.
1 96 140 70 2 48 8 5 12 6 80 14 28 35 24 16 42 10 20 32 21
-
$\begingroup$ Impressive find. I spent half the day trying to improve upon it before resorting to programming. I was on the right track, but the solutions had a distribution of factors I had overlooked. $\endgroup$ Apr 16 at 21:09
$\begingroup$
$\endgroup$
1
I think the largest number among the distinct 21 numbers is 432. Consider the set of lines make a product of the form p^5q^5. Created a star based on the product and the largest number is p^3q^4. Putting p=3 and q=2 yields 432.
Thanks @fljx for pointing out the numerical error.
-
2$\begingroup$ Wouldn't p=3, q=2 give you a smaller max number while maintaining the same product? $\endgroup$– fljxApr 16 at 12:08
$\begingroup$
$\endgroup$
3
I also found a
60
Though, this one involves $7$ as a factor, for a product of
$2^4 \times 3^2 \times 5^1 \times 7^1=5040$
The set-up:
24 35 5 6 20 42 40 4 21 56 9 10 30 16 14 15 28 12 48 60 7
Optimality:
There doesn't appear to be any better solutions admitting any of the prime factors 2, 3, 5, 7, and 11.
It's interesting how the problem seems like a non-linear optimisation problem, but, if we consider each entry as a tuple of (its possible prime factors') exponents, we can formulate it as a linear one. All one needs to do is to ensure the tuples are distinct, the sum of some tuple elements are equal, and, for optimality, that no solutions exist when: $$(a,b,c,d,e):= 2^a * 3^b * 5^c * 7^d * 11^e < 60$$ $$\iff a\log(2) + b\log(3) + c\log(5) + d\log(7) + e\log(11)< \log(60)$$
-
1$\begingroup$ Minor note - why can we stop with 11? Because there are at least 5 numbers with each factor - 13 would end up with 65 as one number. $\endgroup$ Apr 17 at 21:25
-
$\begingroup$ @ZizyArcher There are at least 7 numbers with each factor. $\endgroup$ Apr 17 at 23:24
-
$\begingroup$ @DanielMathias You are right, and we don't even need 11. I found ways to have 5 and cover all lines, but I noticed some lines are covered twice - so this isn't a possibility. $\endgroup$ Apr 18 at 6:39