Let \(S(k)\) represent the sum of the digits of the natural number \(k\). A natural number \(a\) is termed \(n\)-good if there exists a sequence of natural numbers \(a_0, a_1, \ldots, a_n\) such that \(a_n = a\) and \(a_{i+1} = a_i - S(a_i)\) for all \(i = 0, 1, \ldots, n - 1\). We want to determine if, for any natural number \(n\), there exists a natural number that is \(n\)-good but not \((n + 1)\)-good.
For natural numbers \(n\) and \(k\), we define the functions \(f(n) = n - S(n)\) and \(f_k(n) = f(f(...(n)...))\) (where \(f\) is applied \(k\) times). When \(n\) is increased by 1, the sum of its digits \(S(n)\) either increases by 1 (if \(n\) does not end with 9) or decreases. This indicates that the function \(f\) is non-decreasing, and the inequality \(f(n + 10) > f(n)\) holds for all \(n\).
First method. Choose a natural number \(d\) such that \(10d > 20d(n + 1)\), and set \(k = 10d\). Define \(b_0 = 10k - 1\) and \(c_0 = 10k - k\), along with \(b_i = f^i(b_0)\) and \(c_i = f^i(c_0)\). We need to demonstrate that the inequality \(b_n > c_n > b_{n+1}\) holds. (*)
Since \(S(c_0) \leq 9k\), we can use induction to show that \(c_i \geq 10k - k - 9ki\). For \(i \leq n + 1\), we have \((9i + 1)k \leq 10ki \leq 10d + 1(n + 1) < 10^{2d}\). This implies that in the number \(c_i\), at least \(k - 2d\) of the leading digits are nines. Therefore, \(S(c_i) \geq 9(k - 2d)\), which leads us, again by induction, to conclude that \(c_i \leq 10k - k - 9(k - 2d)i\). Thus, we obtain the bounds: \(10k - (9i + 1)k \leq c_i \leq 10k - k - 9(k - 2d)i\).
Similarly, we can derive bounds for \(b_i\): \(10k - 9ki - 1 \leq b_i \leq 10k - 1 - 9(k - 2d)i\). To establish the inequality \(c_n < b_n\), it suffices to verify that \(10k - k - 9(k - 2d)n < 10k - 9kn - 1\), which simplifies to \(k > 18dn + 1\). This is satisfied by our choice of \(d\). To show that \(b_{n+1} < c_n\), we need to check that \(10k - 1 - 9(k - 2d)(n + 1) < 10k - (9n + 1)k\), which is equivalent to \(8k + 1 > 18d(n + 1)\), and this is also true.
Since \(c_n = f^n(c_0)\), the number \(c_n\) is \(n\)-good. Furthermore, if \(x \leq b_0\), then \(f^{n+1}(x) \leq f^{n+1}(b_0) = b_{n+1} < c_n\). If \(x > b_0\), then \(f(x) \geq f(10k) = b_0\), which implies \(f^{n+1}(x) \geq f^n(b_0) = b_n > c_n\). Thus, \(c_n\) is not \((n+1)\)-good.
Second method. Assume the contrary: that every \(n\)-good number \(x\) is also \((n+1)\)-good. This means that \(x = f^{n+1}(y)\) for some \(y\). Consequently, the number \(f(y)\) is also \(n\)-good, and thus \((n+1)\)-good; this implies that \(x\) is \((n+2)\)-good. Similarly, we can show that any \(n\)-good number is \((n+k)\)-good for all natural \(k\); we will refer to such numbers simply as good.
Let us select a natural number \(k > 3 \cdot 10^n\) and estimate the number \(D_k\) of good \(k\)-digit numbers in two different ways.
- For each number \(y \in [2 \cdot 10^{k-1}, 10^k)\), the number \(g(y) = f^n(y)\) is good. Moreover, \(g(y) \geq y - 9kn \geq y - 10^{k-1} \geq 10^{k-1}\), indicating that \(g(y)\) is a good \(k\)-digit number. On the other hand, the equation \(f(x) = a\) has at most 10 solutions for any \(a\), hence the equation \(g(y) = a\) has no more than \(10^n\) solutions.
- Let \(x\) be a good \(k\)-digit number. Then \(x = f^{10^k}(y)\) for some \(y\). Since \(f^{10^k}(y) \leq y - 10^k\), the number \(y\) must be at least \((k+1)\)-digit. Let \(s\) be the smallest number for which \(f^s(y)\) is \(k\)-digit. Then \(f^{s-1}(y) \geq 10^k\), which implies \(f^s(y) = f(f^{s-1}(y)) \geq f(10^k) = 10^k - 1\). Thus, \(f^s(y) = 10^k - 1\), meaning that any \(k\)-digit good number can be expressed as \(f^t(10^k - 1)\) for some \(t\).
Now we will demonstrate that the number \(f^t(10^k - 1)\) can be \(k\)-digit only under specific conditions, leading to a contradiction with the estimate from the previous point. Let \(b_0 = 10^k - 1\) and \(b_i = f^i(b_0)\). It suffices to show that \(b_{t_0} < 10^k - 1\).
Assume the contrary; then all numbers \(b_i\) for \(i \leq t_0\) are \(k\)-digit. We will estimate the number of such indices \(i < t_0\) for which \(b_i - b_{i+1} < k\) (i.e., \(S(b_i) < k\)). The digits of any such number \(b_i\) form a sequence of \(k\) non-negative integers whose sum does not exceed \(k - 1\). However, there are exactly \(\binom{k - 1 + k - 1}{k - 1}\) such sequences (this can be easily derived from problem 30719 b). Thus, there are no more than \(\binom{k - 1 + k - 1}{k - 1}\) required indices.
Consequently, in the sequence \(b_0, b_1, \ldots, b_{t_0}\), the next number is less than the previous one by at least \(k\) in at least \(t_0 - 22k - 1\) cases. Note that \(k \cdot 22k - 1 \leq 10^k\). Therefore, \(b_{t_0} \leq b_0 - (t_0 - 22k - 1)k \leq 10^k - 10^k = 0\). This leads to a contradiction.