uniolympiads Ελληνικά

IMC 2014, Day 2, Problem 1

For a positive integer xx, denote its nthn^{\text{th}} decimal digit by dn(x)d_n(x), i.e. dn(x)∈{0,1,…,9}d_n(x) \in \{0, 1, \dots, 9\} and x=∑n=1∞dn(x)10n−1x = \sum_{n=1}^{\infty} d_n(x)10^{n-1}. Suppose that for some sequence (an)n=1∞(a_n)_{n=1}^{\infty}, there are only finitely many zeros in the sequence (dn(an))n=1∞\big(d_n(a_n)\big)_{n=1}^{\infty}. Prove that there are infinitely many positive integers that do not occur in the sequence (an)n=1∞(a_n)_{n=1}^{\infty}.

Original from the official PDFFor a positive integer x , denote its n th de imal digit by d n (x) , i.e. d n (x) ∈ {0, 1, . . . , 9} and x = ∞ P ∞ d n (x)10 n−1 . Suppose that for some sequen e a n n=1 , there are n=1 ∞ only nitely many zeros in the sequen e d n (a n ) n=1 . Prove that there are innitely many positive integers that do not o ur in the sequen e (a n ) ∞ n=1 .

This transcription was compared symbol by symbol with the original, but not yet by a person.

Time on this problem 0:00

Work for at least 45 minutes before opening the solution.

Official solution

(Proposed by Alexander Bolbot, State University, Novosibirsk)

Solution 1. By the assumption there is some index n0n_0 such that dn(an)≠1d_n(a_n) \ne 1 for n≥n0n \ge n_0. We show that

an+1,an+2,…>10nforn≥n0.(1)a_{n+1}, a_{n+2}, \ldots > 10^n \quad\text{for}\quad n \ge n_0. \tag{1}
Notice that in the sum an=∑k=1∞dk(an)10k−1a_n = \sum\limits_{k=1}^{\infty} d_k(a_n)10^{k-1} we have the term dn(an)10n−1d_n(a_n)10^{n-1} with dn(an)≥1d_n(a_n) \ge 1. Therefore, an≥10n−1a_n \ge 10^{n-1}. Then for m>nm > n we have am≥10m>10na_m \ge 10^m > 10^n. This proves (1).

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

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

Assume that dn(an)≠0d_n(a_n) \ne 0 for n>n0n > n_0. Define the sequence of digits

gn={2dn(xn)=11dn(xn)≠1.g_n = \begin{cases} 2 & d_n(x_n) = 1 \\ 1 & d_n(x_n) \ne 1. \end{cases}
Hence gn≠dn(an)g_n \ne d_n(a_n) for every positive integer nn. Let
xk=∑n=1kgn⋅10n−1fork=1,2,….x_k = \sum_{n=1}^{k} g_n \cdot 10^{n-1} \quad\text{for}\quad k = 1,2,\ldots.

As xk+1≥10k>xkx_{k+1} \ge 10^k > x_k, the sequence (xk)(x_k) is increasing and so it contains infinitely many distinct positive integers. We show that the numbers xn0,xn0+1,xn0+2,…x_{n_0}, x_{n_0+1}, x_{n_0+2}, \ldots no not occur in the sequence (an)(a_n); in other words, xk≠anx_k \ne a_n for every pair n≥1n \ge 1 and k≥n0k \ge n_0 of integers.

Indeed, if k≥nk \ge n then dn(xk)=gn≠dn(an)d_n(x_k) = g_n \ne d_n(a_n), so xk≠anx_k \ne a_n.

If n>k≥n0n > k \ge n_0 then dn(xk)=0≠dn(an)d_n(x_k) = 0 \ne d_n(a_n), so xk≠anx_k \ne a_n.

Transcribed from the official solutions, page 1. This transcription has not been checked a second time; if in doubt, look at the original.

Archive problem: the statement is the official text (transcribed, with the original above). Subject classification and difficulty were estimated automatically; hints and a worked solution are added over time.

How did it go?