3

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.

Lord_Farin
  • 17,743
user70810
  • 31
  • 2
    The problem is discussed in detail at http://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
  • 2
    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
  • 2
    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
  • Just will add a link to a beautiful non brute-force solution, https://puzzling.stackexchange.com/questions/46521/maximum-result-with-digits – Roah Mar 28 '19 at 04:18

1 Answers1

0

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$.

Gerry Myerson
  • 179,216