Difference between revisions of "2005 PMWC Problems/Problem I1"
I like pie (talk | contribs) m |
I like pie (talk | contribs) m |
||
| 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 + 2(51) = 111</math> digits in the original number, so after deleting 100 we will be left with <math>11</math> digits. There are six <math>9</math>s in the string of numbers. Applying the greedy algorithm, we might expect to get <math>999999\ldots</math>, but we promptly run out of digits. So instead, we start with 5 nines, <math>99999</math>. 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 | + | 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. There are six <math>9</math>s in the string of numbers. Applying the greedy algorithm, we might expect to get <math>999999\ldots</math>, but we promptly run out of digits. So instead, we start with 5 nines, <math>99999</math>. 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 apparent 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:14, 8 October 2007
Problem
What is the greatest possible number one can get by discarding 
digits, in any order, from the number 
?
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 
digits in the original number, so after deleting 100 we will be left with 
digits. There are six 
s in the string of numbers. Applying the greedy algorithm, we might expect to get 
, but we promptly run out of digits. So instead, we start with 5 nines, 
. 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 apparent that our answer is 
.
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 | ||
