12
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ u forgot to choose right answer :) $\endgroup$ – Oray Oct 2 '18 at 10:22
13
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Correct! But could you explain the "next digit can be at most ..." parts? $\endgroup$ – Rand al'Thor Aug 8 '18 at 11:25
  • $\begingroup$ Added an explanation, plus the answer for the second part. $\endgroup$ – jafe Aug 8 '18 at 11:30
  • 1
    $\begingroup$ You can do better for the second part ... $\endgroup$ – Rand al'Thor Aug 8 '18 at 11:34
  • $\begingroup$ Argh, you're right. $\endgroup$ – jafe Aug 8 '18 at 11:37
  • 1
    $\begingroup$ @jafe I updated your "smallest" answer to reflect your final step; I believe this is right now (and matches the smallest answers of the other answers). Feel free to roll back if this is not what you were intending. $\endgroup$ – El-Guest Aug 8 '18 at 13:27
6
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I think you've miscounted somewhere and removed fewer than 100 digits. The methodology is good though! $\endgroup$ – Rand al'Thor Aug 8 '18 at 11:24
  • $\begingroup$ @Randal'Thor did it fast, let me fix it :D $\endgroup$ – Oray Aug 8 '18 at 11:26
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Which is the same as Oray's answer, which I'd not seen - oops! $\endgroup$ – Phil M Jones Aug 8 '18 at 13:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.