1
$\begingroup$

Maximize :: $A = B \times C$ asks for two decimal numbers which, combined, use the digits from $1$ through $9$ exactly once, and which have the greatest possible product. (Actually, it asks for the product, but I want the factors).

kba's answer to that question suggests a procedure for finding these, but does not provide a rigorous proof that it works.

The maximum product of two numbers which together contain all non-zero digits exactly once is a duplicate with an answer that proves one aspect.

My question

How can we generalize the problem/solution to arbitrary number bases and find a rigorous proof that it works? If possible, come up with further generalizations. For example: what happens if only certain digits may be used? A small bounty will be offered after two days.

$\endgroup$
1
+50
$\begingroup$

The proof comes from showing that if you have two numbers with the same sum, the product is maximized when they are as close as possible. So given $a,b$ with $b \gt a$, choose $c \lt \frac 12{b-a}$. Then $a+c,b-c$ are two numbers with the same sum as $a,b$ and $(a+c)(b-c)=ab+(b-a)c+c^2 \gt ab$. This justifies the construction. The same construction works in any base. In base $16$, for example, we would find $EDB97531 \cdot FCA86420$ If only certain digits can be used, we again do the same construction: paste the next digit onto the smaller of the existing numbers.

$\endgroup$
  • $\begingroup$ There's some setup missing. For starters, how do you know the digits should be divided evenly (4 and 5 for the decimal case) between the numbers? $\endgroup$ – dfeuer Dec 24 '13 at 19:24
  • $\begingroup$ You can do the same proof imagining moving a digit from a 3+6 case. By having 4+5 you get 20 products while having 3+6 you only get 18. Basically it comes down to $1111\cdot 11111-111\cdot 111111=11000$ All those $1$'s will bet multiplied by pairs of digits and you get more of them. $\endgroup$ – Ross Millikan Dec 24 '13 at 19:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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