There are two sequences of natural numbers. The first sequence consists of all natural numbers that do not contain a particular digit, in ascending order. The second sequence consists of all the remaining natural numbers in ascending order. Every natural number occurs exactly once in exactly one of the sequences.

How many terms are there in the first sequence such that each of those terms is greater than the corresponding term at the same position in the second sequence?

[SOLVED]

2 comments

Gnanasenthil G solved this puzzle:

There are infinitely many terms in the first sequence such that each of those terms is greater than the corresponding term at the same position in the second sequence.

Let \(S_1\) be a sequence of all natural numbers that do not contain a particular digit \(d\), in ascending order. Let \(S_2\) be a sequence of all natural numbers that contain the digit \(d\). There are two cases to consider.

  1. \(d = 0\)
  2. \(1 \leq d \leq 9\)

Let us consider the first case in which \(d = 0\). Let \(f(n)\) represent the number of numbers less than \(10^n\) that are present in \(S_1\). Let \(g(n)\) represent the number of numbers less than \(10^n\) that are present in \(S_2\).

The number of \(k\)-digit natural numbers that do not contain the digit \(0\) is \(9^k\). Thus,

\begin{align*} & f(n) = \sum_{k = 1}^n 9^k = \frac{9 (9^n - 1)}{8}, \\ & g(n) = 10^n - 1 - f(n) = 10^n - \frac{9 (9^n - 1)}{8} - 1. \end{align*}

Thus, the largest \(n\)-digit natural number occurs at the \(f(n)\)th position in \(S_1\). For \(n = 1\), \(f(n) = 9\) and \(g(n) = 0\). For \(n > 1\), since the \(f(n)\)th number of \(S_1\) is the largest \(n\)-digit natural number, it must be greater than the \(g(n)\)th number of \(S_2\). Therefore, when \(f(n) \leq g(n)\), the \(f(n)\)th number of \(S_1\) is greater than the \(f(n)\)th number of \(S_2\). We can show that \(f(n) \leq g(n)\) when \(n \geq 8\).

\begin{align*} n \geq 8 & \implies n \gt \frac{\log 9 - \log 4}{\log 10 - \log 9} \\ & \implies \log 9 - \log 4 \lt n (\log 10 - \log 9) \\ & \implies \log \frac{9}{4} \lt n \log \frac{10}{9} \\ & \implies \frac{9}{4} \lt \left(\frac{10}{9}\right)^n \\ & \implies 9^n - 1 \lt \frac{4}{9} \cdot 10^n \\ & \implies 2 \cdot \frac{9}{8} \cdot (9^n - 1) \lt 10^n \\ & \implies \frac{9}{8} \cdot (9^n - 1) \lt 10^n - \frac{9}{8} \cdot (9^n - 1) \\ & \implies f(n) \lt g(n) + 1 \\ & \implies f(n) \leq g(n). \end{align*}

Therefore, for every \(n \geq 8\), the \(f(n)\)th number of \(S_1\) is greater than the \(f(n)\)th number of \(S_2\).

Now let us consider the second case in which \(1 \leq d \leq 9\). Let \(f(n)\) represent the number of numbers less than \(10^n\) that are present in \(S_1\). Let \(g(n)\) represent the number of numbers less than \(10^n\) that are present in \(S_2\). The number of \(k\)-digit natural numbers that do not contain the digit \(d\) is \(8 \cdot 9^{k - 1}\). Thus,

\begin{align*} & f(n) = \sum_{k = 1}^n 8 \cdot 9^{k - 1} = 9^n - 1, \\ & g(n) = 10^n - 1 - f(n) = 10^n - 9^n. \end{align*}

The \(\bigl(f(n) + 1\bigr)\)th number in \(S_1\) is an \((n + 1)\)-digit number whereas \(g(n)\)th number in \(S_2\) is an \(n\)-digit number. Therefore, when \(f(n) \lt g(n)\), the \(\bigl(f(n) + 1\bigr)\)th number in \(S_1\) is greater than the \(\bigl(f(n) + 1\bigr)\)th number in \(S_2\). We can show that \(f(n) \lt g(n)\) when \(n \geq 7\).

\begin{align*} n \geq 7 & \implies n \geq \frac{\log 2}{\log 10 - log 9} \\ & \implies \log 2 \lt n (\log 10 - \log 9) \\ & \implies 2 \lt \left(\frac{10}{9}\right)^n \\ & \implies 2 \cdot 9^n \lt 10^n \\ & \implies 9^n \lt 10^n - 9^n \\ & \implies f(n) \lt g(n). \end{align*}

Therefore, for every \(n \geq 7\), the \(\bigl(f(n) + 1\bigr)\)th number of \(S_1\) is greater than the \(\bigl(f(n) + 1\bigr)\)th number of \(S_2\).

Susam Pal from cotpi added:

Here is how I solved the problem by using the facts that the harmonic series diverges and Kempner series converges. Nicole Oresme, a 14th century philosopher, presented a very simple proof of divergence of the harmonic series. It is presented as theorem 1 below. Then Kempner's proof of convergence of Kempner's series is presented as theorem 2 below. Finally, I've used these two results to solve this problem in theorem 3.

Theorem 1. \(\sum_{n=1}^\infty \frac{1}{n}\), also known as the harmonic series, diverges.

Proof. Beginning with the third term of the harmonic series, grouping the terms of the harmonic series in blocks of \(2, 4, 8, 16, \dots\) terms, we can show that the sum of the terms in each block is greater than \(\frac{1}{2}\).

\begin{align*} \sum_{n=1}^\infty \frac{1}{n} & = 1 + \frac{1}{2} + \left(\frac{1}{3} + \frac{1}{4}\right) + \left(\frac{1}{5} + \frac{1}{6} + \frac{1}{7} + \frac{1}{8}\right) + \dots \\ & \gt 1 + \frac{1}{2} + \left(\frac{1}{4} + \frac{1}{4}\right) + \left(\frac{1}{8} + \frac{1}{8} + \frac{1}{8} + \frac{1}{8}\right) + \dots \\ & = 1 + \frac{1}{2} + \frac{1}{2} + \frac{1}{2} + \dots = \infty. \end{align*}

More concisely,

\begin{align*} \sum_{n=1}^\infty \frac{1}{n} & = 1 + \sum_{k = 0}^\infty \sum_{n = 2^k + 1}^{2^{k + 1}} \frac{1}{n} \\ & \gt 1 + \sum_{k = 0}^\infty \sum_{n = 2^k + 1}^{2^{k + 1}} \frac{1}{2^{k + 1}} \\ & = 1 + \sum_{k = 0}^\infty 2^k \cdot \frac{1}{2^{k + 1}} \\ & = 1 + \sum_{k = 0}^\infty \frac{1}{2} = \infty. \end{align*}

Theorem 2. The series obtained from the harmonic series by removing all terms containing a digit \(d\) in their denominators, also known as Kempner series, converges.

Proof. Let \(f_d(n)\) represent the sum of the reciprocals of all \(n\)-digit natural numbers that do not contain the digit \(d\). Thus, Kempner series can be written as \(\sum_{n=1}^\infty f_d(n)\).

If \(d = 0\), there are exactly \(9^n\) \(n\)-digit natural numbers that do not contain the digit \(d\), and except \(10^{n - 1}\) each is greater than \(10^{n - 1}\). Therefore, \(f_0(n) \lt \frac{9^n}{10^{n - 1}}\) and the Kempner series is

\[ \sum_{n=1}^\infty f_0(n) \lt \sum_{n=1}^\infty \frac{9^n}{10^{n - 1}} = 9 \sum_{n=1}^\infty \frac{9^{n - 1}}{10^{n - 1}} = 90. \]

Similarly, if \(1 \leq d \leq 9\), there are exactly \(8 \cdot 9^{n - 1}\) \(n\)-digit natural numbers that do not contain the digit \(d\), and therefore, \(f_d(n) \lt 8 \cdot \frac{9^{n - 1}}{10^{n - 1}}\) and the Kempner series is

\[ \sum_{n=1}^\infty f_d(n) \lt 8 \sum_{n=1}^\infty \frac{9^{n - 1}}{10^{n - 1}} = 80. \]

Since all terms of the Kempner series are positive and the series is bounded, it is convergent.

Theorem 3. Let \((a_1, a_2, a_3, \dots)\) denote the sequence of all natural numbers that do not contain a digit \(d\), in ascending order. Let \((b_1, b_2, b_3, \dots)\) denote the sequence of all natural numbers that contain the digit \(d\), in ascending order. Then there are infinitely many integers \(a_i\) such that \(a_i \gt b_i\) where \(i\) is a positive integer.

Proof. Let \(S_a = \sum_{n=1}^\infty \frac{1}{a_n}\) and \(S_b = \sum_{n=1}^\infty \frac{1}{b_n}\). By the definition of the sequences \((a_1, a_2, \dots)\) and \((b_1, b_2, \dots)\), \(S_a\) represents Kempner series and \(S_a + S_b\) represents the harmonic series.

Let us assume that there are only a finite number of numbers \(a_i\) such that \(a_i \gt b_i\). Further, let us assume that there are exactly \(k\) such numbers.

Since \(a_i\) and \(b_i\) are positive integers, when \(a_i \gt b_i\), \(\frac{1}{b_i} - \frac{1}{a_i} \lt 1\). This implies that \(\frac{1}{b_i} \lt 1 + \frac{1}{a_i}\) when \(a_i \gt b_i\). When \(a_i \lt b_i\), \(\frac{1}{b_i} \lt \frac{1}{a_i}\). From these two results and the assumption that there are exactly \(k\) numbers \(a_i\) such that \(a_i \gt b_i\), we obtain

\[ \sum_{n=1}^\infty \frac{1}{b_n} \lt k + \sum_{n=1}^\infty \frac{1}{a_n} \] This can be rewritten as \[ S_b \lt k + S_a. \]

From theorem 2, we know that \(S_a\) converges. Since every term of \(S_b\) is positive and it is bounded by \(k + S_a\), \(S_b\) must converge too. This implies that \(S_a + S_b\) must converge, but \(S_a + S_b\) is the harmonic series which diverges as per theorem 1. This is a contradiction. Therefore, our assumption that there are only a finite number of numbers \(a_i\) such that \(a_i \gt b_i\) must be false.

Credit

This is an original puzzle from cotpi.

Further reading

The following is a list of resources on related topics:

Post a comment

RSS