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 "2005 PMWC Problems/Problem I1"

(sol)
 
m (→‎Solution)
Line 3: Line 3:
  
 
== Solution ==
 
== Solution ==
−
The length of the resulting number is the same no matter what, so to maximize the number we want to invoke the [[greedy algorithm]] - get as many 9s in the first several digits as possible. There are <math>9 + 5(20) + 2 = 111</math> numbers, so after deleting 100 we will be left with <math>11</math> digits. Now the number of nines is <math>6</math>. Applying the greety algorith, we might expect to get <math>99999\ldots</math>, but we promptly run out of digits. So instead, we start with 5 nines, <math>99999</math>. Naturally we would then try to fit an 8 next, but again it turns out that we run out of digits. So we continue with 7. We still need five more digits, and we have six left to choose from. It quickly becomes apparant that our answer is <math>99999785960</math>.
+
The length of the resulting number is the same no matter what, so to maximize the number we want to invoke the [[greedy algorithm]] - get as many 9s in the first several digits as possible. There are <math>9 + 2(51) = 111</math> digits in the original number, so after deleting 100 we will be left with <math>11</math> digits. Now the number of nines is <math>6</math>. Applying the greety algorithm, we might expect to get <math>99999\ldots</math>, but we promptly run out of digits. So instead, we start with 5 nines, <math>99999</math>. Naturally we would then try to fit an 8 next, but again it turns out that we run out of digits. So we continue with 7. We still need five more digits, and we have six left to choose from. It quickly becomes apparant that our answer is <math>99999785960</math>.
  
 
== See also ==
 
== See also ==
 
{{PMWC box|year=2005|before=First question|num-a=I2}}
 
{{PMWC box|year=2005|before=First question|num-a=I2}}

Revision as of 22:24, 1 October 2007

Problem

What is the greatest possible number one can get by discarding $100$ digits, in any order, from the number $123456789101112\ldots585960$?

Solution

The length of the resulting number is the same no matter what, so to maximize the number we want to invoke the greedy algorithm - get as many 9s in the first several digits as possible. There are $9 + 2(51) = 111$ digits in the original number, so after deleting 100 we will be left with $11$ digits. Now the number of nines is $6$. Applying the greety algorithm, we might expect to get $99999\ldots$, but we promptly run out of digits. So instead, we start with 5 nines, $99999$. Naturally we would then try to fit an 8 next, but again it turns out that we run out of digits. So we continue with 7. We still need five more digits, and we have six left to choose from. It quickly becomes apparant that our answer is $99999785960$.

See also

2005 PMWC (Problems)
Preceded by
First question 		Followed by
Problem I2
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
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2005_PMWC_Problems/Problem_I1&oldid=17348"