15
$\begingroup$

Using each of the digits 1,2,3,4,5,6,7,8,9 exactly once, create three 3-digit numbers such that their product is a maximum.

$\endgroup$
  • 1
    $\begingroup$ Has a correct answer been given? If so, please don't forget to $\color{green}{\checkmark \small\text{Accept}}$ it :) $\endgroup$ – Rubio Mar 2 at 2:46
15
$\begingroup$

The answer is:

941 * 852 * 763 = 611721516

Here's the intuition:

We definitely want the largest numbers (7, 8, 9) in the hundreds place. So, we have 9__, 8__, 7__. Second, we look at 23 * 10 = 230 vs 20 * 13 = 260. As you can see, putting a higher value in lower places increases the product, provided that the lower place is within another number. So, we want to put 9_1 or 91_. We see that 9_1 will provide a higher value in the product, because we want something higher than 1 in the tens place. Following this logic again, we get 8_2 and 7_3. So, we have: 9_1, 8_2, 7_3. With similar logic, we can deduce that the 4 must go in 941, and the 5 must go in 852. So, we get 941, 852, 763. Multiplying them all together, we have 611721516.

Finally, here's

A program that I used to verify the solution:

 import itertools
 permutations = []
 permutations.extend(itertools.permutations([1,2,3,4,5,6],6))
 max_product = 0
 for (a, b, c, d, e, f) in permutations:
   one = 900 + 10 * a + b
   two = 800 + 10 * c + d
   three = 700 + 10 * e + f
   product = one * two * three
   if product > max_product:
     print(one,"*",two,"*",three,"=",product)
   max_product = max(product, max_product)
 
The output is:
 912 * 834 * 756 = 575019648
 912 * 834 * 765 = 581865120
 912 * 843 * 765 = 588144240
 912 * 853 * 764 = 594343104
 921 * 853 * 764 = 600208332
 931 * 852 * 764 = 606013968
 941 * 852 * 763 = 611721516
 
As you can see, the output converges to the final answer.

|improve this answer|||||
$\endgroup$
  • 1
    $\begingroup$ Good answer. I'm not sure it's correct to talk about convergence, though, since you're simply enumerating all the possibilities and picking the largest one. $\endgroup$ – Eric Duminil Feb 12 at 10:29
  • 1
    $\begingroup$ It's more of a convergence of the "current answer" at any given point of time to a global maximum found by enumeration of all possibilities, but you're right that there's some inaccuracy in discussing it that way. $\endgroup$ – Avi Feb 12 at 14:24
3
$\begingroup$

The answer is

$941*852*763 = 611721516$

as @avi already mentioned. But here is my justification:

We can consider that a solution is "locally" a maximum if by switching any pair of digits, we cannot increase the products. Within that framework one can focus on a single product => which one is greater between $(980+a)*(b*100+c)$ and $(900+b*10+a)*(800+c)$ if $b \leq 7$? It can be seen that the difference between both first factors is $d = 10*(8-b)$ whereas the difference between both second factors $100*(b-8) = -d*10$. So both products can be rewritten as $x*y$ and $(x - d)*(y + 10*d) = x*y+(x*10-y)*d-10*d*d > x*y$ if $d < (x*10-y)/10 = x - y/10$ which is totally the case here since $d = 10*(8-b) < 70$ and $x - y/10 = 980+a - b*10 - c/10 > 900$.

The conclusion is that

For any value of $b \leq 7$, so that $d > 0$, it is better, for any choice of $a$ and $c < 100$ to decrease one factor by $d$ if it allows to increase the other factor by $d*10$, which is the case when you prefer 9__*8__ over 98_*___.

Now we know that the 9 digits are splitted in 3 groups

$(9,8,7)$ in the hundreds place, $(6,5,4)$ in the middle and $(1, 2, 3)$ in the unit place.

It now remains to form the three factors by picking one digit in each group.

Switching two digits that are at the same place in two factors amount to increase one by the difference between both digits and decreasing the other by the same difference

Using a similar reasoning

we compare $x*y$ with $(x-d)*(y+d) = x*y + (x-y)*d - d*d > x*y if x-y > d > 0$. But $x-y > 100$ whereas $d < 100$ implies that decreasing the larger factor by the same amount the smaller factor is increased yields a higher product.

As a result, the three factors formed for the three groups are such that

they minimize their distance to each other, i.e., the smallest number starting by $9$ is $941$ and the largest number starting by $7$ is $763$. In the middle, we have the number with the $3$ remaining digits : $852$.

|improve this answer|||||
$\endgroup$
  • $\begingroup$ Great answer. I did it programatically and it proves your answer through a posteriori. $\endgroup$ – Zaenille Feb 14 at 3:23
2
$\begingroup$

We can calculate: $ (a*100 + b*10 + c)*(d*100 + e*10 + f)*(g*100 + h*10 + i)= \\ = adg1000000 + (adh+aeg+bdg)100000 + (adi+aeh+bdh+afg+beg+cdg)10000 + (aei+bdi+afh+beh+cdh+bfg+ceg)1000 + (afi+bei+cdi+bfh+ceh+cfg)100 + (bfi+cei+cfh)10 + cfi $

If we now maximise coefficients in order:

$max(adg)$

a = 9
d = 8
g = 7

$max(adh+aeg+bdg) = max(72h+63e+56b)$

h = 6
e = 5
b = 4

$max(adi+aeh+bdh+afg+beg+cdg) = max(72i+63f+56c)$

i = 3
f = 2
c = 1

We obtain the (correct) solution. But how to formally show that we can maximise independently?

|improve this answer|||||
$\endgroup$
0
$\begingroup$

By simply trying out a couple of combinations, I found:

942 * 763 * 851 = 611,652,846

Some of the other combinations I tried are:

943 * 761 * 852 = 611,414,796
951 * 843 * 762 = 610,890,066
942 * 861 * 753 = 610,729,686
963 * 852 * 741 = 607,972,716
987 * 654 * 321 = 207,204,858

My methodology:

I kept the largest numbers (7, 8, 9) in the 100's column, then the next largest number (4, 5, 6) in the 10's column, and the smallest numbers (1, 2, 3) in the 1's column, then tried to make the largest numbers multiply against each other.
As you can see in the last example, without the largest number in the 100's column, you get a much smaller number.

Edit: FYI, I did the calculations by hand, rather than with a program, so I didn't try all options.

|improve this answer|||||
$\endgroup$
0
$\begingroup$

If we set x=9 then we have x*(x-4)*(x-8)=45

(x-1)(x-5)(x-7)=64

(x-2)(x-3)(x-6)=126

so I obtain 951*842*763=610966146

My opinion is that if we obtain minimum results from the multiplications of monomials, then we will obtain the maximum product of the three 3-digit numbers.

|improve this answer|||||
$\endgroup$
0
$\begingroup$

Another one of those puzzles you can brute force, and therefore would have a coding answer.

The answer is:

941x852x763 with a product of 611721516

Try online

Brute force code:

function permut(string) {
  if (string.length < 2) return string; // This is our break condition

  var permutations = []; // This array will hold our permutations
  for (var i = 0; i < string.length; i++) {
    var char = string[i];

    // Cause we don't want any duplicates:
    if (string.indexOf(char) != i) // if char was used already
      continue; // skip it this time

    var remainingString = string.slice(0, i) + string.slice(i + 1, string.length); //Note: you can concat Strings via '+' in JS

    for (var subPermutation of permut(remainingString))
      permutations.push(char + subPermutation)
  }
  return permutations;
}

let allPermutations = permut('123456789');
let max = {
  product: 0,
  a: 0,
  b: 0,
  c: 0
};

allPermutations.forEach((combination)=>{
    let a = parseInt(combination.substring(0,3));
    let b = parseInt(combination.substring(3,6));
    let c = parseInt(combination.substring(6,9));

    let product = a*b*c;

    if(product>max.product){
      max = {
        product: product,
        a: a,
        b: b,
        c: c
      }
    }
});

console.log(max);
|improve this answer|||||
$\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.