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…)

Is there a general rule, when the number of digits is not five? Certainly we want to spread out the large digits, but how exactly?

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s