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\)?
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.
Remove five \(9\)s, five \(8\)s, five \(7\)s, one \(6\), and one \(4\).
Remove five \(9\)s, five \(8\)s, five \(7\)s, and two \(5\)s.
Remove five \(9\)s, five \(8\)s, four \(7\)s, two \(6\)s, and one \(5\).
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\).