Delete 100 digits

From the 1954 Moscow Maths Olympiad:

Delete 100 digits from the number 123456789101112…979899100 (that is, the number formed by writing the first 100 positive integers next to each other).

What is the largest possible number that could remain?

__________

This is one of those rare problems that I just had to try before doing anything else! The premise is so simple, and the prerequisite knowledge so minimal, that you could give this problem to someone aged 9 or 99 and they could make a decent attempt at it.

The original number contains 192 digits, so deleting 100 of them will leave a 92-digit number.

Idea: get as many digit 9s to the front as I possibly can.

The first five digit 9s in the original number come from 9, 19, 29, 39, 49. I could pick these five 9s to be the first five digits of my new number. That would leave the 103 digits “50515253…9899100” that come after the 49, from which I need to choose 87 digits (to make the total number of digits 92). So my new number will definitely start “99999…”

Can I start with six digit 9s? The sixth 9 would come from 59 in the original number, but then only 83 digits of the original number remain, and I need another 86 digits – no good.

Can I start “999998…”? Well, that 8 would come from 58 in the original number, but then only 85 digits of the original number remain, and I still need another 86 digits – close, but not close enough.

Can I start “999997…”? This time that 7 would come from 57 in the original number. I still need another 86 digits, but now I have 87 digits of the original number to choose from – SUCCESS!

All that remains it to delete one digit from “58596061…9899100”. If I delete the leading digit 5, I will be left with an 8 at the front. Otherwise, I will be left with a 5 at the front. So I should delete the leading 5.

Therefore, the biggest number that can possibly remain after deleting 100 digits is

\boxed{999997859606162...979899100}

This is a wonderful problem: the answer is not immediately obvious, but comes out after a little bit of thought, and absolutely no high-powered mathematics is required to solve it.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s