A place value puzzle

Fawn Nguyen, a middle-school math teacher, has written on finding the greatest product of a three-digit number and a two-digit number made up from some set of five digits. For example: if you’re given the digits 8, 7, 5,4, and 2, you’d have (to pick a product at random) $745 \times 82 = 61090$ . The question is to write the largest possible such product (ideally without doing the multiplication explicitly).

In this case it’s pretty obvious that if you can make one factor larger by just switching around its digits, you should do it: so $754 \times 82 > 745 \times 82$ . But how can you move around the digits between the factors? Which is larger, $854 \times 72$ or $\latex 754 \times 82$? The trick here is to rewrite as $10 \times 85.4 \times 72$ and $10 \times 75.4 \times 82$ , and recall that of two pairs of numbers with the same sum, the ones closer together have a larger product. That is, $(x-a)(x+a) > (x-b)(x+b)$ if and only if $a<b$ . Since $85.4 + 72 = 75.4 + 82$ , we can conclude that $85.4 \times 72 < 75.4 \times 82$ .

So $754 \times 82$ is larger. But now we can switch the 2 and the 4 by the same sort of logic: $754 + 82 = 752 + 84$ and so $754 \times 82 < 752 \times 84$ . This, it turns out, is the best we can do, as we can check by brute force – but how do we know this holds up generally? I haven’t used the differences between digits explicitly, only their ordering, so perhaps everything only depends on the order of the digits. Let’s let our digits be $a, b, c, d, e$ , with $a > b > c > d > e$ . Then there are just ten possible products to look at if we’re trying to find the largest once, since the digits in each factor have to be increasing:

$abc \times de, abd \times ce, abe \times cd, acd \times be, ace \times bd, ade \times bc, bcd \times ae, bce \times ad, bde \times ac, cde \times ab$ .

(Note to pedants: juxtaposition of letters means juxtaposition of the corresponding digits, so when I write $ad$ I mean $10a + d$ , and so on.)

We want to show that $bce \times ad$ is the largest of these products. We can make “moves” of the form $bde \times ac = 100 \times b.de \times ac > 100 \times c.de \times ab = cde \times ab$ , for example, to show that it’s larger than $cde \times ab$; the inequality in the middle follows from $b.de + ac = c.de + ab$ . If I’m not mistaken, any time two of these ten products differ by just switching two letters we can prove an inequality between them. And after a seriously grungy case analysis (which I won’t bore you all with) I believe we get that $bce \times ad$ is always the largest product. In any case, for this particular problem there are only ${9 \choose 5} = 126$ possibilities so you could check by brute force. (Not a good exercise for people who you’re trying to teach to think about place value, but also not a bad programming exercise…)