1

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.

Community
  • 1
dfeuer
  • 9,069

1 Answers1

1

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.

Ross Millikan
  • 374,822
  • 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? – dfeuer Dec 24 '13 at 19:24
  • 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. – Ross Millikan Dec 24 '13 at 19:34