1997 PMWC Problems/Problem I14

From AoPSWiki

Problem

If we make five two-digit numbers using the digits $0, 1, 2, \ldots 9$ exactly once, and the product of the five numbers is maximized, find the greatest number among them.

Solution

This is a greedy algorithm question. Let $a_{1}, b_{1}$ be the digits of the first number, etc. Without loss of generality let $10a_1 + b_1$ be the greatest number. Then we want to maximize the quantity

$(10a_1 + b_1)(10a_2 + b_2) \cdots (10a_5 + b_5)$ $=10^5 a_1a_2a_3a_4a_5 + 10^4(b_1a_2a_3a_4a_5 + \ldots) + \ldots + b_1b_2b_3b_4b_5$

The greedy algorithm quickly tells us that the first digits of the numbers should be $9,8,7,6,5$ , so $a_1 = 9$ . Now, look at the coefficient of $10^4$ . The product $a_2a_3a_4a_5$ is less than any of the other terms (which all contain the maximal $a_1 = 9$ ), so by the greedy algorithm, we should make $b_1$ as small as possible. Hence $b_1 = 0$ , and our answer is $90$ .

1997 PMWC (Problems)
Preceded by Problem I13	Followed by Problem I15
I: 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 T: 1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10

Personal tools

Navigation

Search

Toolbox

1997 PMWC Problems/Problem I14

From AoPSWiki

Problem

Solution

See also