Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1997 PMWC Problems/Problem I14"

(New page: 90)
 
m
Line 1: Line 1:
−
90
+
== Problem ==
 +
If we make five two-digit numbers using the digits <math>0, 1, 2, \ldots 9</math> 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 <math>a_{1}, b_{1}</math> be the digits of the first number, etc. [[Without loss of generality]] let <math>10a_1 + b_1</math> be the greatest number. Then we want to maximize the quantity
 +
 
 +
<cmath>(10a_1 + b_1)(10a_2 + b_2) \cdots (10a_5 + b_5)</cmath>
 +
<cmath>=10^5 a_1a_2a_3a_4a_5 + 10^4(b_1a_2a_3a_4a_5 + \ldots) + \ldots + b_1b_2b_3b_4b_5</cmath>
 +
 
 +
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 also ==
 +
{{PMWC box|year=1997|num-b=I13|num-a=I15}

Revision as of 15:38, 9 October 2007

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$.

See also

{{PMWC box|year=1997|num-b=I13|num-a=I15}

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1997_PMWC_Problems/Problem_I14&oldid=17728"