Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "2007 iTest Problems/Problem 41"

(Created page with "== Problem == The sequence of digits <math>123456789101112131415161718192021\ldots</math> is obtained by writing the positive integers in order. If the <math>10^{nth}</math> dig...")
 
(Solution to Problem 41 — exhausting and satisfying NT problem)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
  
−
The sequence of digits <math>123456789101112131415161718192021\ldots</math> is obtained by writing the positive integers in order. If the <math>10^{nth}</math> digit in this sequence occurs in the part of the sequence in which the m-digit numbers are placed, define <math>f(n)</math> to be <math>m</math>. For example, <math>f(2) = 2</math> because the <math>100^{\text{th}}</math> digit enters the sequence in the placement of the two-digit integer <math>55</math>. Find the value of <math>f(2007)</math>.  
+
The sequence of digits <math>123456789101112131415161718192021\ldots</math> is obtained by writing the positive integers in order. If the <math>10^{nth}</math> digit in this sequence occurs in the part of the sequence in which the m-digit numbers are placed, define <math>f(n)</math> to be <math>m</math>. For example, <math>f(2) = 2</math> because the <math>100^{\text{th}}</math> digit enters the sequence in the placement of the two-digit integer <math>55</math>. Find the value of <math>f(2007)</math>.
 +
 
 +
==Solution==
 +
 
 +
To begin, we can find out for what values of <math>n</math> result in a certain <math>f(n)</math> (or <math>m</math>).  A table can help organize the findings.
 +
 
 +
{|class="wikitable" style="margin-left: auto; margin-right: auto;"
 +
|-
 +
|<math>m</math>
 +
|Number of digits that make up <math>m</math>-digit numbers
 +
|Highest value of <math>n</math> where <math>f(n) = m</math>
 +
|-
 +
|<math>1</math>
 +
|<math>9</math>
 +
|<math>9</math>
 +
|-
 +
|<math>2</math>
 +
|<math>180</math>
 +
|<math>189</math>
 +
|-
 +
|<math>3</math>
 +
|<math>2700</math>
 +
|<math>2889</math>
 +
|-
 +
|<math>4</math>
 +
|<math>36000</math>
 +
|<math>38889</math>
 +
|-
 +
|<math>5</math>
 +
|<math>45 \cdot 10^4</math>
 +
|<math>488889</math>
 +
|}
 +
 
 +
It seems as if for a given value <math>m</math>, highest <math>n</math> where <math>f(n) = m</math> 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>
 +
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.
 +
 
 +
<br>
 +
Note that the last <math>m</math> digits of <math>10^{m} \cdot 9m</math> are zeroes, so the last <math>m</math> digits are still <math>\underbrace{888 \cdots 8}_{m-1 \text{ digits}} 9</math>.  The preceding string of digits are <math>m-1+9m+9 = 10m + 8</math>.  The first string of digits are the string of digits of <math>m</math>, and it is followed by <math>m</math> eights and a nine, so the inductive step is complete.
 +
 
 +
<br>
 +
Using the new discovery, the highest <math>n</math> where <math>f(n) = 2007</math> has <math>4 + 2006 + 1 = 2011</math> digits, the highest <math>n</math> where <math>f(n) = 2003</math> has <math>4 + 2002 + 1 = 2007</math> digits, and the highest <math>n</math> where <math>f(n) = 2004</math> 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>n</math> where <math>f(n) = 2004</math>), <math>f(10^{2007}) = \boxed{2004}</math>.
 +
 
 +
==See Also==
 +
{{iTest box|year=2007|num-b=40|num-a=42}}
 +
 
 +
[[Category:Intermediate Number Theory Problems]]
  
 
== Solution ==
 
== Solution ==

Revision as of 17:12, 2 July 2018

Problem

The sequence of digits $123456789101112131415161718192021\ldots$ is obtained by writing the positive integers in order. If the $10^{nth}$ digit in this sequence occurs in the part of the sequence in which the m-digit numbers are placed, define $f(n)$ to be $m$. For example, $f(2) = 2$ because the $100^{\text{th}}$ digit enters the sequence in the placement of the two-digit integer $55$. Find the value of $f(2007)$.

Solution

To begin, we can find out for what values of $n$ result in a certain $f(n)$ (or $m$). A table can help organize the findings.

$m$ Number of digits that make up $m$-digit numbers Highest value of $n$ where $f(n) = m$
$1$ $9$ $9$
$2$ $180$ $189$
$3$ $2700$ $2889$
$4$ $36000$ $38889$
$5$ $45 \cdot 10^4$ $488889$

It seems as if for a given value $m$, highest $n$ where $f(n) = m$ is a string of digits with $n-1$ followed by $n-1$ 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 $n$ where $f(n) = m$ is the string of digits $(m-1) \underbrace{888 \cdots 8}_{m-1 \text{ digits}} 9$ There are $((10^{m+1} - 1) - (10^{m} + 1)) \cdot (m+1) = 10^{m} \cdot 9(m+1)$ (the string of digits $9(m+1)$ followed by $m$ zeroes) digits that make up $(m+1)$ digit numbers.


Note that the last $m$ digits of $10^{m} \cdot 9m$ are zeroes, so the last $m$ digits are still $\underbrace{888 \cdots 8}_{m-1 \text{ digits}} 9$. The preceding string of digits are $m-1+9m+9 = 10m + 8$. The first string of digits are the string of digits of $m$, and it is followed by $m$ eights and a nine, so the inductive step is complete.


Using the new discovery, the highest $n$ where $f(n) = 2007$ has $4 + 2006 + 1 = 2011$ digits, the highest $n$ where $f(n) = 2003$ has $4 + 2002 + 1 = 2007$ digits, and the highest $n$ where $f(n) = 2004$ has $4 + 2003 + 1 = 2008$ digits. Since $10^{2007}$ has $2008$ digits and $10^{2007}$ is less than $2003\underbrace{888 \cdots 8}_{2003 \text{ digits}} 9$ (highest $n$ where $f(n) = 2004$), $f(10^{2007}) = \boxed{2004}$.

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

Solution

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=2007_iTest_Problems/Problem_41&oldid=95749"