# Quick multiplication puzzle

August 4, 2009 am31 12:47 am

Heard this before, but heard it again today:

1. Rearrange the digits 1, 2, 3, 4, and 5 into a 3-digit number and a 2-digit with the greatest possible product.

2. The solution is slightly counter-intuitive. Explain it so it makes sense.

3. Solve the same puzzle, but with the digits 1, 3, 5, 7 and 9.

Advertisements

9 Comments
leave one →

Or try with digits 1 through 9, and a 5-digit and a 4-digit number.

9652 * 87431=843884012

Not quite! You can transpose a couple of digits in your answer to yield a slightly greater product.

Definitely a counter-intuitive question. Even knowing how to distribute the “big” numbers, I still had to check among a couple of possibilities just to be sure.

If you consider the rearrangment inequality the result seems quite intuitive.

Nick, can you go into more detail. I definitely find this counter-intuitive, and wouldn’t mind another way to look at it.

Jonathan

OK, I didn’t want to give too much of a spoiler yesterday…

Clearly we must begin with 5 as the first digit of one number and 4 as the first digit of the other. Then we continue to use a greedy algorithm to place the remaining digits. Taking the 3 and the 2, we place the 3 opposite the 5, so that the partial products from cross-multiplication are 5*3 and 4*2, which the rearrangement inequality tells us will be greater than 5*2 + 4*3. So now we have 52 and 43. Finally (and similarly) we place the remaining digit 1 opposite the larger pair: 52, giving 52 and 431. (52 * 431 – 521 * 43 = (52 – 43) * 1 = 9.) The same pattern applies in the other example, yielding 93 * 751.

Agreeing with the clearly we must begin with 5 as the first digit of one number and 4 as the first digit of the other, the first thought might be that you want a bigger 3-digit number and thus use 5nn.

The second thought is that if you use 4nn and 5n, I get to use the 5 as a factor 3 times instead of just 2.

The most important choice after the first digits is the second digit of each number! For the same reason that we chose 5 and 4 as the first digits, we should choose 3 and 2 as the second digits. (If you’re not convinced of that, at least there’s only one possibility to check out: 51 × 432, because placing 1 as the second digit of the 3-digit number would give us 51x, where x > 1, but clearly 5×1 > 51x.)

So now we must consider which way round we assign the second digits — will it be 53 × 42 or 52 × 43? The difference between the two choices will clearly be greater than that due to the final digit, 1, when we get around to placing it. It’s easy enough to calculate 52 × 43 = 2236 > 2226 = 53 × 42, but we don’t need to actually perform the multiplication to see that the first product is larger.

Consider:

52 × 43 = (50 + 2) × (40 + 3) = 5×4×10^2 + (5×3 + 4×2)×10 + 2×3, and

53 × 42 = (50 + 3) × (40 + 2) = 5×4×10^2 + (5×2 + 4×3)×10 + 2×3.

Clearly, the only difference lies in the partial products that are multiplied by 10. So which is bigger, 5×3 + 4×2 or 5×2 + 4×3? Again, we don’t need to actually perform the arithmetic to see that the former is bigger. We can use the rearrangement inequality.

The rearrangement inequality states that given two sequences of the same length, the maximal product when you multiply them together occurs when they are both sorted the same way. For example, if the sequences are (10, 5, 1) and (2, 3, 4), the maximal product is 10×4 + 5×3 + 1×2. This becomes intuitively obvious when you imagine being presented with a pile of ten, five and one dollar bills, and being told you can take 2 of one denomination, 3 of another, and 4 of the third!

In the above case, the sequences are (5, 4) and (3, 2), and the rearrangement inequality tells us that 5×3 + 4×2 is the bigger product.

So we have 52 and 43. Now we must decide where to place the 1. There are various ways to see that placing the 1 after 43 will give the larger product. For instance:

52 × 431 = (52 × 43 × 10) + (52 × 1), whereas

521 × 43 = (52 × 43 × 10) + (43 × 1) is clearly smaller.

Alternatively, we could imagine placing both a 1 and a 0, whereupon the rearrangement inequality tells us to place the 1 after 43, because our two sequences would be (52, 43) and (1, 0), and so 52×1 + 43×0 > 52×0 + 43×1.

The advantage of using the rearrangement inequality is that it allows us to easily generalize the solution to any five digits, or to nine digits, as I suggested above.