# Problem of the Week Problem E and Solution Discarding Digits

## Problem

Stef forms the integer $$N$$ by writing the integers from $$1$$ to $$50$$ in order.

That is,

$$N=1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950.$$

Stef then selects some of the digits in $$N$$ and discards them, so that the remaining digits, in their original order, form a new integer. The sum of the digits in this new integer is $$200$$.

If $$M$$ is the largest integer that Stef could have formed, what are the first ten digits of $$M$$?

## Solution

We start by determining the sum of the digits of $$N$$. This is the same as determining the sum of the digits of the numbers from $$1$$ to $$50$$. The digits $$0$$ to $$9$$ sum to $$0 +1 + 2+3 + 4 + 5+ 6+7 +8 + 9 = 45$$.

The digits in the numbers $$10$$ to $$19$$ sum to $$(1+0)+(1+1)+(1+2)+(1+3)+(1+4)+(1+5)+(1+6)+(1+7)+(1+8)+(1+9)$$
$$= 10(1) + (0+1+2+3+4+5+6+7+8+9) = 10+45 = 55$$.

The digits in the numbers $$20$$ to $$29$$ sum to $$(2+0)+(2+1)+(2+2)+(2+3)+(2+4)+(2+5)+(2+6)+(2+7)+(2+8)+(2+9)$$
$$= 10(2) + (0+1+2+3+4+5+6+7+8+9) = 20+45 = 65$$.

Similarly, the digits in the numbers $$30$$ to $$39$$ sum to $$10(3) + 45 = 75$$ and the digits in the numbers $$40$$ to $$49$$ sum to $$10(4) + 45 = 85$$.

We must add $$5$$ and $$0$$ in order to account for the number $$50$$ at the end of $$N$$. Therefore, the sum of the digits of $$N$$ is $$45 + 55+ 65+75+85 + (5+0) = 330$$.

Since the digits of $$M$$ sum to $$200$$, the digits that are removed and discarded must sum to $$330-200 = 130$$.

In order for $$M$$ to be as large as possible, we need $$M$$ to have as many digits as possible. So we need to remove as few digits as possible such that the digits that are removed sum to $$130$$. To determine the fewest number of digits to remove, we remove the largest digits in $$N$$.

We notice that in $$N$$ there are five $$9$$s, five $$8$$s, and five $$7$$s. These $$15$$ digits have a sum of $$5\times 9 + 5\times 8 + 5\times 7=120$$. After removing these digits, we would still need to remove additional digits that have a sum of $$130-120=10$$. We would need at least two more digits to do this. So the fewest number of digits that we can remove that will have a sum of $$130$$ is $$17$$.

So which $$17$$ digits do we remove? We are left with the following four options.

1. Remove five $$9$$s, five $$8$$s, five $$7$$s, one $$6$$, and one $$4$$.

2. Remove five $$9$$s, five $$8$$s, five $$7$$s, and two $$5$$s.

3. Remove five $$9$$s, five $$8$$s, four $$7$$s, two $$6$$s, and one $$5$$.

4. Remove five $$9$$s, four $$8$$s, five $$7$$s, and three $$6$$s.

These are the only ways to remove $$17$$ digits from $$N$$ that have a sum of $$130$$. Thus, each option will result in a number that is exactly $$17$$ digits shorter than $$N$$. So to determine which option results in the largest possible number, we can look at how each affects the first few digits of $$N$$.

Option 1: Remove five $$9$$s, five $$8$$s, five $$7$$s, one $$6$$, and one $$4$$.
After removing all the $$9$$s, $$8$$s, and $$7$$s, the remaining digits start $$123456101112 \ldots$$.

• Removing a $$6$$ and a $$4$$ from anywhere after the first six digits will result in a number whose first six digits are $$123456$$.

• Removing the first $$6$$, and a $$4$$ from anywhere past this $$6$$ will result in a number whose first $$6$$ digits are $$123451$$.

• Removing the first $$4$$, and a $$6$$ from anywhere else in the number will result in a number whose first $$6$$ digits are $$123510$$ or $$123561$$.

Since $$123561>123510>123456>123451$$, removing the first $$4$$, and a $$6$$ from anywhere else in the number can result in a number whose first six digits are $$123561$$. This would result in the largest possible number so far.

Option 2: Remove five $$9$$s, five $$8$$s, five $$7$$s, and two $$5$$s.
After removing all the $$9$$s, $$8$$s, and $$7$$s, the remaining digits start $$123456101112 \ldots$$. No matter how we remove two $$5$$s, we are not able to get a number whose first six digits are larger than $$123561$$. Thus, this option will not result in the largest possible value of $$M$$.

Option 3: Remove five $$9$$s, five $$8$$s, four $$7$$s, two $$6$$s, and one $$5$$.
After removing all the $$9$$s and $$8$$s, the remaining digits start $$1234567101112 \ldots$$. No matter how we remove four $$7$$s, two $$6$$s, and one $$5$$, we are not able to get a number whose first six digits are larger than $$123561$$. Thus, this option will not result in the largest possible value of $$M$$.

Option 4: Remove five $$9$$s, four $$8$$s, five $$7$$s, and three $$6$$s.
After removing all the $$9$$s and $$7$$s, the remaining digits start $$1234568101112 \ldots$$. No matter how we remove four $$8$$s, and three $$6$$s, we are not able to get a number whose first six digits are larger than $$123561$$. Thus, this option will not result in the largest possible value of $$M$$.

Therefore, in order to form the largest possible value of $$M$$, we should remove all $$9$$s, $$8$$s, and $$7$$s, the first $$4$$, and a $$6$$ from anywhere else in the number.

After removing the $$9$$s, $$8$$s, $$7$$s, and the first $$4$$, we are left with $123561011121314151611120212223242526222303132333435363334041424344454644450$ We still must remove a $$6$$ to bring our digit sum to $$200$$. We want whatever $$6$$ we remove to affect the size of the final number in the least possible way. We need to therefore remove the $$6$$ with the lowest place value. The $$6$$ to be removed is therefore the hundred thousands digit in the number shown just above. After removing this $$6$$, $M=12356101112131415161112021222324252622230313233343536333404142434445444450$ It follows that the first $$10$$ digits of $$M$$ are $$1235610111$$.