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:
for the maximum product numbers should be 4-digit and 5-digit
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.
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$.