Maths Olympiad Prep

Library / /24 of 26

Algebra Difficulty 5.5 AIME, harder Prove it United States

Problem:

We use the digits 1,2,,91, 2, \ldots, 9 once each to form two integers (e.g., 74197419 and 8263582635). What two integers formed in this way have the greatest product? Prove your answer.

Solution

Solution:

The answer is 9642×875319642 \times 87531.

Place value is an important feature of this problem, but it's awkward to write about since the leading digits matter most, yet we do not know how many digits each number will have. As a workaround, let us prepend "0." to the two integers we are forming, making them into decimals. For example, 74197419 and 8263582635 would become 0.74190.7419 and 0.826350.82635. Regardless of how many digits our two integers have, the effect is to divide their product by 10910^{9}. Thus, whichever decimals formed in this way have the largest product will correspond to the integers that have the largest product in the original formulation of the problem. The benefit of this transformation is that the leading digits now have a definite place value of tenths, etc.

It is clear that the digits of each decimal should be in descending order (otherwise we can increase that number by rearranging them). Less obviously, a larger digit should never be assigned a lower place value in one decimal than the place value assigned to a smaller digit in the other decimal. For example, we should not form the decimals 0.980.98\ldots and 0.70.7\ldots, where the larger 88 is assigned a place value of hundredths while the smaller 77 is assigned a place value of tenths.

Proof: Let our two decimals be xx and yy, let digit dd have place value 10a10^{-a} in decimal xx, and let digit ee have place value 10b10^{-b} in decimal yy, where d>ed>e and a>ba>b. Then swapping these two digits increases the product of the two decimals by (de)(10by10ax)=(de)(10a)(10abyx)(d-e)\left(10^{-b} y-10^{-a} x\right) = (d-e)\left(10^{-a}\right)\left(10^{a-b} y-x\right). Since 0.1x,y<10.1 \leq x, y < 1, we have y>101xy > 10^{-1} x, and therefore the increase is positive.

As a result of the foregoing, we see that the tenths digits of our two decimals must be 99 and 88 (in some order), the hundredths digits must be 77 and 66 (in some order), the thousandths must be 55 and 44, the ten-thousandths 33 and 22, and the hundred-thousandths 11 (and 00). Now the sum of the two decimals is fixed, so their product is maximized by making the two numbers as close to each other as possible. This is achieved by 0.96420.9642 and 0.875310.87531, and we are done.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.