IMC 2014 · Day 2 · P6

By the assumption there is some index $n_0$ such that $d_n(a_n) \ne 1$ for $n \ge n_0$. We show that $$\tag{1} a_{n+1}, a_{n+2}, \dots > 10^n \quad \text{for } n \ge n_0.$$ Notice that in the sum $a_n = \sum\limits_{k=1}^{\infty} d_k(a_n) 10^{k-1}$ we have the term $d_n(a_n) 10^{n-1}$ with $d_n(a_n) \ge 1$. Therefore, $a_n \ge 10^{n-1}$. Then for $m > n$ we have $a_m \ge 10^m > 10^n$. This proves (1).

From (1) we know that only the first $n$ elements, $a_1, a_2, \dots, a_n$ may lie in the interval $[1, 10^n]$. Hence, at least $10^n - n$ integers in this interval do not occur in the sequence at all. As $\lim (10^n - n) = \infty$, this shows that there are infinitely many numbers that do not appear among $a_1, a_2, \dots$.

We will use Cantor's diagonal method to construct infinitely many positive integers that do not occur in the sequence $(a_n)$.

Assume that $d_n(a_n) \ne 0$ for $n > n_0$. Define the sequence of digits $$g_n = \begin{cases} 2 & d_n(x_n) = 1 \\ 1 & d_n(x_n) \ne 1. \end{cases}$$ Hence $g_n \ne d_n(a_n)$ for every positive integer $n$. Let $$x_k = \sum_{n=1}^{k} g_n \cdot 10^{n-1} \quad \text{for } k = 1, 2, \dots.$$ As $x_{k+1} \ge 10^k > x_k$, the sequence $(x_k)$ is increasing and so it contains infinitely many distinct positive integers. We show that the numbers $x_{n_0}, x_{n_0+1}, x_{n_0+2}, \dots$ no not occur in the sequence $(a_n)$; in other words, $x_k \ne a_n$ for every pair $n \ge 1$ and $k \ge n_0$ of integers.

Indeed, if $k \ge n$ then $d_n(x_k) = g_n \ne d_n(a_n)$, so $x_k \ne a_n$.

If $n > k \ge n_0$ then $d_n(x_k) = 0 \ne d_n(a_n)$, so $x_k \ne a_n$.