Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

This question already has an answer here:

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.

share|cite|improve this question

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

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

The problem is discussed in detail at – 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

1 Answer 1

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

share|cite|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.