# 2007 iTest Problems/Problem 41

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

## 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 digits of the string is part of an $m$-digit number. A table can help organize the findings.

 $m$ Number of digits that make up $m$-digit numbers Highest value of $p$ where the $p^\text{th}$ digit of the string is part of an $m$-digit number $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 $p$ where the $p^\text{th}$ digit of the string is part of an $m$-digit number 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 $p$ where the $p^\text{th}$ digit of the string is part of an $m$-digit number is the string of digits $(m-1) \underbrace{888 \cdots 8}_{m-1 \text{ digits}} 9$. The number of digits that make up $(m+1)$ digit numbers is $((10^{m+1} - 1) - (10^{m} + 1)) \cdot (m+1) = 10^{m} \cdot 9(m+1)$, which is the string of digits $9(m+1)$ followed by $m$ zeroes.

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 $p$ where the $p^\text{th}$ digit of the string is part of an $2007$-digit number has $4 + 2006 + 1 = 2011$ digits, the highest $p$ where the $p^\text{th}$ digit of the string is part of an $2003$-digit number has $4 + 2002 + 1 = 2007$ digits, and the highest $p$ where the $p^\text{th}$ digit of the string is part of an $2004$-digit number 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 $p$ where the $p^\text{th}$ digit of the string is part of an $2004$-digit number), $f(2007) = \boxed{2004}$.