Problem 12 · 2017 Math Kangaroo
Medium
Number Theory
place-valuecasework
Tom writes the numbers from 1 to 20 one after another and gets the 31-digit number 1234567891011121314151617181920. He then deletes 24 of the digits so that the number that is left is as large as possible. Which number does he get?
Show answer
Answer: C — 9781920
Show hints
Hint 1 of 2
Keeping 7 digits in their original left-to-right order, you want the largest possible number.
Still stuck? Show hint 2 →
Hint 2 of 2
Greedily grab the biggest digit you can while leaving enough digits to fill the remaining places.
Show solution
Approach: greedy choice of the largest leftmost digits
- The string 1234567891011121314151617181920 has 31 digits; deleting 24 leaves 7.
- To maximise, pick the largest digit early while keeping enough digits after it to complete 7.
- The best run grabs the 9 (from the '...891...'), then 7 and 8 (from '17'/'18'), then 1920.
- This gives 9781920 (C).
Mark:
· log in to save