Number Problem to Find Maximum Possible Product

Date: 02/01/2005 at 00:17:38
From: Sudha
Subject: To find the maximum product....

Hi.  My question is:

Use all the digits from 1 to 9 without repeating, to form two numbers
such that their product is maximum.  A digit used should be unique
across both the numbers.  For example, the numbers formed could be
1234 and 56789.

I don't know the logic or how to proceed.  It's obvious we cannot use
brute force method.

Date: 02/01/2005 at 02:35:02
From: Doctor Achilles
Subject: Re: To find the maximum product....

Hi Sudha,

Thanks for writing to Dr. Math.

The first thing I notice about this problem is that when we are 
designing our numbers we always want to put the digits in order from
largest to smallest.

For example, let's say we decide that the best way to proceed is to
use the digits: 1,2,3,4 in the first number and 5,6,7,8,9 in the
second.  We will get the smallest possible answer if we have these two
numbers:

  1234 and 56789

And a larger answer if we have:

  3421 and 89756

But we will get the largest answer possible using the digits that way
if we have:

  4321 and 98765

So for starters, let's not even consider any number that doesn't have
the largest digit first, etc.

So if we ever had a number like

  98756

as an option, we would automatically replace it with

  98765

to get a larger number.

Ok, now let's start with a simple case:

  98765432 and 1

This gives us a product of 98,765,432.

Now, unlike most of the members of the Math Forum, I am a scientist,
not a mathematician.  So I like to do experiments.  I sometimes find
that if I can't find an equation to get me the right answer directly,
I can figure it out scientifically.  The way you do an experiment is
you change one variable and leave the rest alone.

EXPERIMENT 1:

For our first experiment, let's leave the first number as an 8-digit
number and the second number as a 1-digit number.  But let's put our
biggest digit (9) in the first number.  So now we have:

  87654321 and 9

This gives us a product of 788,888,889.

So what have we learned from this experiment?  It pays to put your
biggest digit in your smallest number.

EXPERIMENT 2:

Now let's try another experiment.  Let's see if we can do better with
a 7-digit number and a 2-digit number:

  8765432 and 91

This gives us 797,654,312.  So we're improving.

So we've learned from this experiment that a 7-digit number plus a
2-digit number is better than an 8-digit number and a 1-digit number.

EXPERIMENT 3:

For now, let's just work with a 2-digit and 7-digit number.  We may be
able to do better than that later, but we'll worry about that later.

At this point, I would hypothesize that we can do better by replacing
the "1" in our second number with a larger number.

Sure enough,

  8765431 * 92 = 806,419,652

So we've learned from this experiment that it helps to increase the
second digit of the smaller number.

EXPERIMENT 4:

There are three alternatives possible that the last experiment presents:

Alternative A: the best 2-digit second number would be 98 because it
maximizes the second number.

Alternative B: the best 2-digit second number would be 97 because even
though we learned from experiment 1 to put our biggest digit in our
smaller number, it may be important to put our second biggest digit
(8) in the bigger number.

Alternative C: some other 2-digit number is better.

Let's test the first two alternatives:

  7654321 * 98 = 750,123,458

  8654321 * 97 = 839,469,137

So, we actually do a lot worse if we take the 8 out of our larger
number.  But we do pretty good (the best we've done so far) by making
97 our smaller number.

So what we've learned from this experiment is it is best to have your
second-largest digit in the larger number.

Ok, so up to this point we know we need to put the 8 in our larger
number and the 9 in the smaller number.

What is left to answer:

1) Should the 7 go in the smaller number?  Or would something like 96
or 95 make a better 2 digit number?  Once you find the best 2-digit
number, you will know a few other digits that belong in the small
number and a few others that belong in the big number.

2) How many digits should be in the smaller number?  Is 2 the best we
can do?  Should there be 3? 4?  (Note that there can't be 5 digits
because then it wouldn't be the smaller number any more.)

3) If we need more than 2 digits in the small number, which should
they be?  The small number already has 9, we know it shouldn't
have 8.  Should the small number get 7 or does the large number need
it?  Which number gets 6?  Which gets 5?  Which gets 4?  Which gets 3?
 Which gets 2?

Try experimenting around further to see what you get.

Hope this helps.  I'd be happy to hear back from you if you have ideas
or if you want to check some of your work with me.

- Doctor Achilles, The Math Forum
  http://mathforum.org/dr.math/ 

Date: 02/01/2005 at 02:57:32
From: Sudha
Subject: To find the maximum product....

Hi -

I tried your method and got the answer!  Thanks for the logic.