Difference between revisions of "2007 iTest Problems/Problem 41"
Rockmanex3 (talk | contribs) m (→Solution) |
Rockmanex3 (talk | contribs) (Better phrasing) |
||
Line 37: | Line 37: | ||
<br> | <br> | ||
− | For the inductive step, assume the highest <math>n</math> where <math>f(n) = m</math> is the string of digits <math>(m-1) \underbrace{888 \cdots 8}_{m-1 \text{ digits}} 9</math>. | + | For the inductive step, assume the highest <math>n</math> where <math>f(n) = m</math> is the string of digits <math>(m-1) \underbrace{888 \cdots 8}_{m-1 \text{ digits}} 9</math>. The number of digits that make up <math>(m+1)</math> digit numbers is <math>((10^{m+1} - 1) - (10^{m} + 1)) \cdot (m+1) = 10^{m} \cdot 9(m+1)</math>, which is the string of digits <math>9(m+1)</math> followed by <math>m</math> zeroes. |
− | |||
<br> | <br> |
Revision as of 17:17, 2 July 2018
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 values of result in a certain (or ). A table can help organize the findings.
Number of digits that make up -digit numbers | Highest value of where | |
It seems as if for a given value , highest where 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 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 has digits, the highest where has digits, and the highest where has digits. Since has digits and is less than (highest where ), .
See Also
2007 iTest (Problems, Answer Key) | ||
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 |