Difference between revisions of "2007 iTest Problems/Problem 41"
Rockmanex3 (talk | contribs) (Solution to Problem 41 — exhausting and satisfying NT problem) |
Rockmanex3 (talk | contribs) m (→Solution) |
||
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>. |
There are <math>((10^{m+1} - 1) - (10^{m} + 1)) \cdot (m+1) = 10^{m} \cdot 9(m+1)</math> (the string of digits <math>9(m+1)</math> followed by <math>m</math> zeroes) digits that make up <math>(m+1)</math> digit numbers. | There are <math>((10^{m+1} - 1) - (10^{m} + 1)) \cdot (m+1) = 10^{m} \cdot 9(m+1)</math> (the string of digits <math>9(m+1)</math> followed by <math>m</math> zeroes) digits that make up <math>(m+1)</math> digit numbers. | ||
Revision as of 18:12, 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 ![]() |
Highest value of ![]() ![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
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
.
There are
(the string of digits
followed by
zeroes) digits that make up
digit numbers.
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 |