4
$\begingroup$

The numbers $x_1,$ $x_2,$ $x_3,$ $y_1,$ $y_2,$ $y_3,$ $z_1,$ $z_2,$ $z_3$ are equal to the numbers $1,$ $2,$ $3,$ $\dots,$ $9$ in some order. Find the smallest possible value of $$x_1 x_2 x_3 + y_1 y_2 y_3 + z_1 z_2 z_3.$$

I would assume the lowest number, $1,$ would have to be multiplied by $9,$ the highest. I do not know how to approach this with AM-GM, though.

$\endgroup$
7
  • $\begingroup$ You in fact can have a proof by exhaustion... A dirty trick $\endgroup$ – user12986714 May 10 '20 at 1:22
  • $\begingroup$ Sorry, is there a slick way to do this? I don't really want to brute force, though I can. $\endgroup$ – Frost Bite May 10 '20 at 1:23
  • $\begingroup$ I don't want to brute force this problem, but rather to do it smartly. $\endgroup$ – Frost Bite May 10 '20 at 1:30
  • 5
    $\begingroup$ $\sqrt[3]{9!}\approx 70.327$ and $3\times\sqrt[3]{9!}\approx 213.98$, so $72+72+70=214$ should be minimal $\endgroup$ – Daniel Mathias May 10 '20 at 1:34
  • 1
    $\begingroup$ $9\cdot8\cdot 1 + 6\cdot 5 \cdot 2 +4\cdot3\cdot 7= 72+60+84=216$ is also pretty close. $\endgroup$ – mechanodroid May 10 '20 at 1:53
1
$\begingroup$

The following Mathematica script confirms that there is only one solution:

prod[p_] := p[[1]] p[[2]] p[[3]] + p[[4]] p[[5]] p[[6]] + p[[7]] p[[8]] p[[9]];
perms = Permutations[{1, 2, 3, 4, 5, 6, 7, 8, 9}];
unique = Select[perms, (#[[1]] < #[[2]] < #[[3]] && #[[4]] < #[[5]] < #[[6]] && #[[7]] < #[[8]] < #[[9]] && #[[1]] < #[[4]] < #[[7]]) &];
products = Map[prod, unique];
min = Min[products];
result = Select[unique, (prod[#] == min) &];
Print[min, " ", result]

The script prints:

214 {{1, 8, 9, 2, 5, 7, 3, 4, 6}}

The next best two solutions are:

215 {{1, 7, 9, 2, 5, 8, 3, 4, 6}}
216 {{1, 8, 9, 2, 5, 6, 3, 4, 7}, {1, 8, 9, 2, 6, 7, 3, 4, 5}}
$\endgroup$
0
$\begingroup$

This isn't as systematic or as linear as I'd like but:

$\frac {M+N+P}3 \le \sqrt[3]{MNP}=\sqrt[3]{9!}\approx 71.3$ and equality is closest when the $w_1w_2w_3$ clusters are each closet to the geometric mean of $71.3$.

So we must have one term contaning the $9$. That is, wolog, $9x_1x_2 \approx 71.3$ so $x_1x_2 \approx 7.9$. Clearly the best option is $x_1x_2 = 8$ and $x_1,x_2 = 2,4$ or $1,8$.

$1,8$ has the advantage as it simultaneously finds clusters for the far off values of $1$ and $8$ as well.

In any event we also have to find, wolog, $7y_1y_2 \approx 71.3$ so $y_1x_2\approx 10.1$ and the best solution for that is $7,2,5$.

So with $9,1,8$ and $7,2,5$ that leaves $z_1, z_2, z_3 = 3,4,6$ and $3*4*6=72$ with our clusters being $70, 72, 72$ around our geometric mean of $71.3$ the only possible smaller sum would be be a tighter cluster and the only tighter cluster that is smaller it $71,71,71$, which is not an option.

So we can be assured that is the least.

We were "lucky" though

Still if say we had gotten something pretty close first, say,

$9*8*1 + 6*5*2 + 7*4*2 = 72 + 60 + 84$ we could see if we can improve it be attempting to finding a tighter cluster of values closer to $71.3$, than $60$ and $84$ are. The contenders that can formed by trios less than or equal to $9$ are:

$63=7*1*9; 64=8*2*4; 70=7*2*5; 72=9*8*1=9*2*4=6*3*4;80=8*2*5$ ... and it would take brute force to choose among those. But even among that we want to get as close to $71.3$ as possible and we have $3$ ways to do $72$ and one way to do $70$.... well, that screams to uss to look if two of the ways to do $72$ are mutually compatible with the way to do $70$.

$\endgroup$

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.