The maximum product of two numbers which together contain all non-zero digits exactly once [duplicate]

I found the following puzzle:

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 know that the answer is 9642 and 87531.

It is obvious that digits should form the numbers in descending order.

I've spent so much time trying to prove that:

1. for the maximum product numbers should be 4-digit and 5-digit

2. why people use greedy algorithm for solving the puzzle so that they start from the first digit and add one by one other digits?

Thank you.

-

marked as duplicate by MJD, Lost1, Daniel Robert-Nicoud, egreg, Yiorgos S. SmyrlisFeb 17 '14 at 17:52

The problem is discussed in detail at mathforum.org/library/drmath/view/67763.html – Gerry Myerson Jun 17 '13 at 12:14
they use brute force solution( – user70810 Jun 17 '13 at 12:21
Also, if you type "9642 and 87531" into Google you will find many places where the problem has been discussed. – Gerry Myerson Jun 17 '13 at 12:27
Dear Gerry, I used google before posting here) All the solutions start with "it is obvious that for the maximum product numbers should be 4-digit and 5-digit" and use greedy algorithm. For me it's not obvious, sorry( – user70810 Jun 17 '13 at 13:14

I'll consider the bit about the maximum requiring a 4-digit and a 5-digit number. I'll show you can't do better with a 2-digit times a 7-digit number, and leave the other cases as an exercise.

So, suppose $a$ is a 2-digit number, and $b$ a 7-digit number. Now consider the 4-digit number $a'$ and the 5-digit number $b'$ you get by chopping off the last two digits of $b$ and appending them to $a$. These two digits form a number, $x$, and we have $$a'=100a+x,\quad b'={b-x\over100}$$ and $$a'b'=\cdots{\rm algebra}\dots=ab+{b-100a-x\over100}$$ Now $b\ge1,000,000$; $100a\le100,000$; $x\le100$ so the fraction in the display is positive and $a'b'\gt ab$.

-