2007 iTest Problems/Problem 41
Contents
Problem
The sequence of digits is obtained by writing the positive integers in order. If the digit in this sequence occurs in the part of the sequence in which the m-digit numbers are placed, define to be . For example, because the digit enters the sequence in the placement of the two-digit integer . Find the value of .
Solution
To begin, we can find out for what digits of the string is part of an -digit number. A table can help organize the findings.
Number of digits that make up -digit numbers | Highest value of where the digit of the string is part of an -digit number | |
It seems as if for a given value , highest where the digit of the string is part of an -digit number is a string of digits with followed by eights and a nine. To prove that this is the case, we use induction. The base case for both of our wanted outcomes is seen in the table.
For the inductive step, assume the highest where the digit of the string is part of an -digit number is the string of digits . The number of digits that make up digit numbers is , which is the string of digits followed by zeroes.
Note that the last digits of are zeroes, so the last digits are still . The preceding string of digits are . The first string of digits are the string of digits of , and it is followed by eights and a nine, so the inductive step is complete.
Using the new discovery, the highest where the digit of the string is part of an -digit number has digits, the highest where the digit of the string is part of an -digit number has digits, and the highest where the digit of the string is part of an -digit number has digits. Since has digits and is less than (highest where the digit of the string is part of an -digit number), .
See Also
2007 iTest (Problems) | ||
Preceded by: Problem 40 |
Followed by: Problem 42 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 • 26 • 27 • 28 • 29 • 30 • 31 • 32 • 33 • 34 • 35 • 36 • 37 • 38 • 39 • 40 • 41 • 42 • 43 • 44 • 45 • 46 • 47 • 48 • 49 • 50 • 51 • 52 • 53 • 54 • 55 • 56 • 57 • 58 • 59 • 60 • TB1 • TB2 • TB3 • TB4 |