Removing 100 digits from the first 100 numbers

Question

Write the first 100 positive integers next to each other to form one big number: $$123456789101112131415161718192021\dots90919293949596979899100.$$ If we remove 100 digits (not necessarily consecutive) from this big number, what is the largest possible number that could remain? And the smallest? (Leading zeroes are not permitted.)

_{Based on a problem from the Moscow Mathematical Olympiad. Seems hard, but the solution is quick and elegant once you spot it.}

Answer 1

The biggest one is

99999785960616263646566676869707172737475767778798081828384858687888990919293949596979899100

Because

We can't influence the number's length (there's a fixed number of digits), so to maximize the value we take the maximal first digit, then second digit etc.

Remove the 84 first non-nines (16 digits left to remove):
999995051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100

The largest number within the next 17 digits is 7, so from here, the next digit in the answer can be at most 7 (we can't remove more than 16 digits). So remove 15 non-7's... (1 digit left to remove): 999997585960616263646566676869707172737475767778798081828384858687888990919293949596979899100

From here, the next digit can be at most 8 so remove one non-8 from the middle: 99999785960616263646566676869707172737475767778798081828384858687888990919293949596979899100

The smallest one is

10000012340616263646566676869707172737475767778798081828384858687888990919293949596979899100

Because

Remove 85 non-zeros (leave leading 1). 15 left...
10000051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100

The smallest number in the next 16 digits is 1. Remove 1 non-1 (14 left to remove):
1000001525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100

The smallest number in the next 15 digits is 2. Remove 1 non-2 (13 left to remove):
100000125354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100

The smallest number in the next 14 digits is 3. Remove 1 non-3 (12 left to remove):
10000012354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100

The smallest number in the next 13 digits is 4. Remove 1 non-4 (11 left to remove):
1000001234555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100

The smallest number in the next 12 digits is 0. Remove 11 non-0's (0 left to remove):
10000012340616263646566676869707172737475767778798081828384858687888990919293949596979899100

Answer 2

First of all, we remove

$100$ digits whatsoever and we cannot change any digit place, so in order to get the biggest or smallest number we need to play with the first digits as big/small as possible. Since 9 is the biggest digit, to make it biggest, we need to try to get as many 9-digit as possible, if somehow it is not possible to get 9 by removing the digits (it will happen examplified below), we need to consider the next biggest digit 8 and etc....

So

To get 9, we need to remove first 8 digits from 123456789101112...,

Then

Remove every 19 digits after 9 because the next 9 is after 19 digits, then look for another 9 and continue removing...

and our number becomes something like below after removing 84 digits:

99999950515253545556575859.......

and we have

16 digit left to remove but we cannot reach to 9 because the next 9 is 19 digits after like before... so we should consider getting 8 in 16 digit, can we reach to 8 with 16 digits? no, then 7? yes after 15 digits luckily..!

so then

remove 15 digits again

then our number becomes:

99999975859..... with 1 digit removing option!

Lastly,

remove $5$ which is between $7$ and $8$, since we dont have 9 after 1 digit, only 8 is biggest possible number!

then the number becomes

9999997859606162....

---

For the smallest one, the same logic is applicable,

Remove numbers until we encounter $0$.

The frequency of

$0$ in the sequence is 19 again

so our number becomes

10000051525354555657585960....

Then we have 15 digits left to remove so with the same principle

if we remove $15$ digits, we will not able to reach $0$, then we should look for $1$.

First

$1$ exists in the next digit, so remove 1 digit only, then look for another one for the 14 digits if we cant find $1$, look for $2$ etc... this is the general methodology to find the biggest or smallest number.

So our number becomes (if I did not mess up)

10000012340616263....

Answer 3

I get the smallest one to be:

10000012340616263646566676869707172737475767778798081828384858687888990919293949596979899100

Method:

By following jafe's first 85 deletions, followed by the "5"s in 51,52,53,54 (leaving 1234), then the next 11 digits up the the "0" of 60.