Difference between revisions of "2007 iTest Problems/Problem 41"
Rockmanex3 (talk | contribs) m (→Solution) |
Rockmanex3 (talk | contribs) |
||
(One intermediate revision by the same user not shown) | |||
Line 5: | Line 5: | ||
==Solution== | ==Solution== | ||
− | To begin, we can find out for what | + | To begin, we can find out for what digits of the string is part of an <math>m</math>-digit number. A table can help organize the findings. |
{|class="wikitable" style="margin-left: auto; margin-right: auto;" | {|class="wikitable" style="margin-left: auto; margin-right: auto;" | ||
Line 11: | Line 11: | ||
|<math>m</math> | |<math>m</math> | ||
|Number of digits that make up <math>m</math>-digit numbers | |Number of digits that make up <math>m</math>-digit numbers | ||
− | |Highest value of <math> | + | |Highest value of <math>p</math> where the <math>p^\text{th}</math> digit of the string is part of an <math>m</math>-digit number |
|- | |- | ||
|<math>1</math> | |<math>1</math> | ||
Line 34: | Line 34: | ||
|} | |} | ||
− | It seems as if for a given value <math>m</math>, highest <math> | + | It seems as if for a given value <math>m</math>, highest <math>p</math> where the <math>p^\text{th}</math> digit of the string is part of an <math>m</math>-digit number is a string of digits with <math>n-1</math> followed by <math>n-1</math> 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. |
<br> | <br> | ||
− | For the inductive step, assume the highest <math> | + | For the inductive step, assume the highest <math>p</math> where the <math>p^\text{th}</math> digit of the string is part of an <math>m</math>-digit number 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> | ||
Line 44: | Line 43: | ||
<br> | <br> | ||
− | Using the new discovery, the highest <math> | + | Using the new discovery, the highest <math>p</math> where the <math>p^\text{th}</math> digit of the string is part of an <math>2007</math>-digit number has <math>4 + 2006 + 1 = 2011</math> digits, the highest <math>p</math> where the <math>p^\text{th}</math> digit of the string is part of an <math>2003</math>-digit number has <math>4 + 2002 + 1 = 2007</math> digits, and the highest <math>p</math> where the <math>p^\text{th}</math> digit of the string is part of an <math>2004</math>-digit number has <math>4 + 2003 + 1 = 2008</math> digits. Since <math>10^{2007}</math> has <math>2008</math> digits and <math>10^{2007}</math> is less than <math>2003\underbrace{888 \cdots 8}_{2003 \text{ digits}} 9</math> (highest <math>p</math> where the <math>p^\text{th}</math> digit of the string is part of an <math>2004</math>-digit number), <math>f(2007) = \boxed{2004}</math>. |
==See Also== | ==See Also== |
Latest revision as of 18:22, 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 digits of the string is part of an -digit number. A table can help organize the findings.
![]() |
Number of digits that make up ![]() |
Highest value of ![]() ![]() ![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
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, 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 |