Difference between revisions of "1997 PMWC Problems/Problem I14"
m (missed }) |
m |
||
Line 10: | Line 10: | ||
The greedy algorithm quickly tells us that the first digits of the numbers should be <math>9,8,7,6,5</math>, so <math>a_1 = 9</math>. Now, look at the coefficient of <math>10^4</math>. The product <math>a_2a_3a_4a_5</math> is less than any of the other terms (which all contain the maximal <math>a_1 = 9</math>), so by the greedy algorithm, we should make <math>b_1</math> as small as possible. Hence <math>b_1 = 0</math>, and our answer is <math>90</math>. | The greedy algorithm quickly tells us that the first digits of the numbers should be <math>9,8,7,6,5</math>, so <math>a_1 = 9</math>. Now, look at the coefficient of <math>10^4</math>. The product <math>a_2a_3a_4a_5</math> is less than any of the other terms (which all contain the maximal <math>a_1 = 9</math>), so by the greedy algorithm, we should make <math>b_1</math> as small as possible. Hence <math>b_1 = 0</math>, and our answer is <math>90</math>. | ||
− | == See | + | == See Also == |
{{PMWC box|year=1997|num-b=I13|num-a=I15}} | {{PMWC box|year=1997|num-b=I13|num-a=I15}} |
Latest revision as of 16:05, 15 May 2012
Problem
If we make five two-digit numbers using the digits 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 be the digits of the first number, etc. Without loss of generality let
be the greatest number. Then we want to maximize the quantity
The greedy algorithm quickly tells us that the first digits of the numbers should be , so
. Now, look at the coefficient of
. The product
is less than any of the other terms (which all contain the maximal
), so by the greedy algorithm, we should make
as small as possible. Hence
, and our answer is
.
See Also
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 |