Difference between revisions of "1997 PMWC Problems/Problem I14"
m |
m |
||
| (One intermediate revision by one other user not shown) | |||
| 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 15: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
![\[(10a_1 + b_1)(10a_2 + b_2) \cdots (10a_5 + b_5)\]](http://latex.artofproblemsolving.com/2/5/9/259ba4da318d0946ebad3341579c468b0e3d3287.png)
![\[=10^5 a_1a_2a_3a_4a_5 + 10^4(b_1a_2a_3a_4a_5 + \ldots) + \ldots + b_1b_2b_3b_4b_5\]](http://latex.artofproblemsolving.com/c/4/0/c4008a58fae521f1e602a73300b16fc45df15071.png)
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 | ||
