Maximizing product of five-digits numbers

Question

From a French 2016 puzzle and math contest, where no calculator is allowed

Using each of the digits $0,1,2,3,4,5,6,7,8,9$ exactly once, find two five-digit integers such that their product is maximal

The contest lasts $3$ hours and this is problem $12$, out of $18$.

I can't an time-efficient approach to solve this.

An obvious requirement is that in each number, the digits come in decreasing order (from left to right). Consequently, the greatest number starts with $9$, and the smallest ends with $0$.

Answer 1

Let $N_1 = 10^4 x_1 + 10^3 x_2 + \cdots x_5$ and $N_2 = 10^4y_1 + \cdots +y_5$. Since $N_1\times N_2 = 10^8 x_1y_1+\cdots$, it is clear that $x_1 = 9, y_1 = 8$. Now, we have \begin{align*} N_1 &= 90000 + 10^3x_2 + \cdots \\ N_2 &= 80000 + 10^3y_2 + \cdots \\ N_1\times N2 &= 72\cdot 10^8 + 10^7(9y_2+8x_2) + 10^6x_2y_2 \cdots \end{align*} To maximize the product, we need to maximize $9y_2+8x_2$. The obvious candidates are $x_2 = 7, y_2 = 6$ and $x_2 = 6, y_2 = 7$. Since $9 \cdot 6 + 8 \cdot 7 = 110$ and $9 \cdot 7 + 8 \cdot 6 = 111$, we choose $x_2 = 6, y_2 = 7$. The numbers so far are $96000 + 10^2x_3+\cdots$ and $87000+10^2y_3+\cdots$. Now we need to maximize $96y_3+87x_3$. The possibilities are $x_3 = 5, y_3 = 4$ or $x_3 = 4, y_3 = 5$. In these cases, $96y_3+87x_3$ has values 819 and 828 respectively. Thus we choose $y_3 = 5, x_3 = 4$. Now we have \begin{align*} N_1 &= 96400 + 10^2x_4 + \cdots \\ N_2 &= 87500 + 10^2y_4 + \cdots \end{align*} Now we need to maximize $964 y_1 + 875 x_4$. Here we see that $x_4 = 2$ and $y_4 = 3$. Finally, we have \begin{align*} N_1 &= 96420 + x_5 \\ N_2 &= 87530 + y_5 \end{align*} Now to maximize $9642 y_5 + 8753 x_5$, clearly $y_5 = 1$ and $x_5 = 0$. Thus the required numbers are $96420$ and $87531$ and the maximum product is $8439739020$.

Answer 2

Let $A = abcde_{10}$ and $B = fghij_{10}$ be the numbers denoted in decimal basis such that the product $p = A \times B$ is maximal. One has : $$ A = 10^4a + 10^3b + 10^2c + 10d + e \\ B = 10^4f + 10^3g + 10^2h + 10i + j$$ By expanding the product $AB$ and factoring by powers of ten, we get $$ p = a(10^8f + 10^7g + 10^6h + 10^5i + 10^4j) \\ + b(10^7f + 10^6g + 10^5h + 10^4i + 10^3j) \\ + c(10^6f + 10^5g + 10^4h + 10^3i + 10^2j) \\ + d(10^5f + 10^4g + 10^3h + 10^2i + 10j) \\ + e(10^4f + 10^3g + 10^2h + 10i + j)$$

As you said,

An obvious requirement is that in each number, the digits come in decreasing order (from left to right)

From this remark and because the term to maximize at any price appears to be $a(10^8f + 10^7g + 10^6g + 10^5i + 10^4j)$, we choose consequently $$ a = 9 \\ f = 8 $$

However, there appears to be a kind of "diagonal choice" to make. As a matter of fact, if we set $g = 7$, we cannot set $b = 7$ anymore. So wet get to chose between whether $9 \times 7.10^7 + b \times 7.10^6 + c\times 7.10^5 + d\times 7.10^4 + e\times 7.10^3$ with $b, c, d, e$ lesser than 7 or $7(8.10^7 + 10^6g + 10^5h + 10^4i + 10^3j)$ with $g, h, i, j$ lesser than 7.

In the best case, that is to say if $b = 6, c= 5, d=4, e=3$, the first case is equal to $675,801,000$ whereas the second is equal to $605,801,000$. Since we want the final sum to be maximal, the best choice is $$g = 7 \\ b = 6$$ By repeating the process successively, one can eventually determine that $$ h = 5 \\ c = 4 \\ i = 3 \\ d = 2 \\ j = 1 \\ e = 0 $$

Hence $A = 96,420$ and $B = 87,531$. Their product is equal to $8,439,739,020$. Computations turn out to be quite easy since they mainly involve powers of ten.