We identify integers $n \geq 2$ with the digit-strings, briefly strings, of their decimal representation and extend the definition of $h$ to all non-empty strings with digits from $0$ to $9$. We recursively define ten functions $f_{0}, \ldots, f_{9}$ that map some strings into integers for $k=9,8, \ldots, 1,0$. The function $f_{9}$ is only defined on strings $x$ (including the empty string $\varepsilon$) that entirely consist of nines. If $x$ consists of $m$ nines, then $f_{9}(x)=m+1$, $m=0,1, \ldots$. For $k \leq 8$, the domain of $f_{k}(x)$ is the set of all strings consisting only of digits that are $\geq k$. We write $x$ in the form $x_{0} k x_{1} k x_{2} k \ldots x_{m-1} k x_{m}$ where the strings $x_{s}$ only consist of digits $\geq k+1$. Note that some of these strings might equal the empty string $\varepsilon$ and that $m=0$ is possible, i.e. the digit $k$ does not appear in $x$. Then we define
$$f_{k}(x)=\sum_{s=0}^{m} 4^{f_{k+1}\left(x_{s}\right)} .$$
We will use the following obvious fact:
Fact 1. If $x$ does not contain digits smaller than $k$, then $f_{i}(x)=4^{f_{i+1}(x)}$ for all $i=0, \ldots, k-1$. In particular, $f_{i}(\varepsilon)=4^{9-i}$ for all $i=0,1, \ldots, 9$.
Moreover, by induction on $k=9,8, \ldots, 0$ it follows easily:
Fact 2. If the nonempty string $x$ does not contain digits smaller than $k$, then $f_{i}(x)>f_{i}(\varepsilon)$ for all $i=0, \ldots, k$.
We will show the essential fact:
Fact 3. $f_{0}(n)>f_{0}(h(n))$.
Then the empty string will necessarily be reached after a finite number of applications of $h$. But starting from a string without leading zeros, $\varepsilon$ can only be reached via the strings $1 \rightarrow 00 \rightarrow 0 \rightarrow \varepsilon$. Hence also the number $1$ will appear after a finite number of applications of $h$.

Proof of Fact 3. If the last digit $r$ of $n$ is $0$, then we write $n=x_{0} 0 \ldots 0 x_{m-1} 0 \varepsilon$ where the $x_{i}$ do not contain the digit $0$. Then $h(n)=x_{0} 0 \ldots 0 x_{m-1}$ and $f_{0}(n)-f_{0}(h(n))=f_{0}(\varepsilon)>0$.
So let the last digit $r$ of $n$ be at least $1$. Let $L=y k$ and $R=z r$ be the corresponding left and right parts where $y$ is some string, $k \leq r-1$ and the string $z$ consists only of digits not less than $r$. Then $n=y k z r$ and $h(n)=y k z(r-1) z(r-1)$. Let $d(y)$ be the smallest digit of $y$. We consider two cases which do not exclude each other.

Case 1. $d(y) \geq k$.
Then
$$f_{k}(n)-f_{k}(h(n))=f_{k}(z r)-f_{k}(z(r-1) z(r-1)) .$$
In view of Fact 1 this difference is positive if and only if
$$f_{r-1}(z r)-f_{r-1}(z(r-1) z(r-1))>0$$
We have, using Fact 2,
$$f_{r-1}(z r)=4^{f_{r}(z r)}=4^{f_{r}(z)+4^{f_{r+1}(\varepsilon)}} \geq 4 \cdot 4^{f_{r}(z)}>4^{f_{r}(z)}+4^{f_{r}(z)}+4^{f_{r}(\varepsilon)}=f_{r-1}(z(r-1) z(r-1)) .$$
Here we use the additional definition $f_{10}(\varepsilon)=0$ if $r=9$. Consequently, $f_{k}(n)-f_{k}(h(n))>0$ and according to Fact 1, $f_{0}(n)-f_{0}(h(n))>0$.

Case 2. $d(y) \leq k$.
We prove by induction on $d(y)=k, k-1, \ldots, 0$ that $f_{i}(n)-f_{i}(h(n))>0$ for all $i=0, \ldots, d(y)$. By Fact 1, it suffices to do so for $i=d(y)$. The initialization $d(y)=k$ was already treated in Case 1. Let $t=d(y)<k$. Write $y$ in the form $u t v$ where $v$ does not contain digits $\leq t$. Then, in view of the induction hypothesis,
$$f_{t}(n)-f_{t}(h(n))=f_{t}(v k z r)-f_{t}(v k z(r-1) z(r-1))=4^{f_{t+1}(v k z r)}-4^{f_{t+1}(v k z(r-1) z(r-1))}>0 .$$
Thus the inequality $f_{d(y)}(n)-f_{d(y)}(h(n))>0$ is established and from Fact 1 it follows that $f_{0}(n)-f_{0}(h(n))>0$.

We identify integers $n \geq 2$ with the digit-strings, briefly strings, of their decimal representation and extend the definition of $h$ to all non-empty strings with digits from $0$ to $9$. Moreover, let us define that the empty string, $\varepsilon$, is being mapped to the empty string. In the following all functions map the set of strings into the set of strings. For two functions $f$ and $g$ let $g \circ f$ be defined by $(g \circ f)(x)=g(f(x))$ for all strings $x$ and let, for non-negative integers $n$, $f^{n}$ denote the $n$-fold application of $f$. For any string $x$ let $s(x)$ be the smallest digit of $x$, and for the empty string let $s(\varepsilon)=\infty$. We define nine functions $g_{1}, \ldots, g_{9}$ as follows: Let $k \in\{1, \ldots, 9\}$ and let $x$ be a string. If $x=\varepsilon$ then $g_{k}(x)=\varepsilon$. Otherwise, write $x$ in the form $x=y z r$ where $y$ is either the empty string or ends with a digit smaller than $k$, $s(z) \geq k$ and $r$ is the rightmost digit of $x$. Then $g_{k}(x)=z r$.

Lemma 1. We have $g_{k} \circ h=g_{k} \circ h \circ g_{k}$ for all $k=1, \ldots, 9$.

Proof of Lemma 1. Let $x=y z r$ be as in the definition of $g_{k}$. If $y=\varepsilon$, then $g_{k}(x)=x$, whence
$$g_{k}(h(x))=g_{k}\left(h\left(g_{k}(x)\right)\right.$$
So let $y \neq \varepsilon$.

Case 1. $z$ contains a digit smaller than $r$.
Let $z=u a v$ where $a<r$ and $s(v) \geq r$. Then
$$h(x)= \begin{cases}yuav & \text{if } r=0 \\ yuav(r-1) v(r-1) & \text{if } r>0\end{cases}$$
and
$$h\left(g_{k}(x)\right)=h(z r)=h(u a v r)= \begin{cases}uav & \text{if } r=0 \\ uav(r-1) v(r-1) & \text{if } r>0\end{cases}$$
Since $y$ ends with a digit smaller than $k$, the equality is obviously true.

Case 2. $z$ does not contain a digit smaller than $r$.
Let $y=u v$ where $u$ is either the empty string or ends with a digit smaller than $r$ and $s(v) \geq r$. We have
$$h(x)= \begin{cases}u v z & \text{if } r=0 \\ u v z(r-1) v z(r-1) & \text{if } r>0\end{cases}$$
and
$$h\left(g_{k}(x)\right)=h(z r)= \begin{cases}z & \text{if } r=0 \\ z(r-1) z(r-1) & \text{if } r>0\end{cases}$$
Recall that $y$ and hence $v$ ends with a digit smaller than $k$, but all digits of $v$ are at least $r$. Now if $r>k$, then $v=\varepsilon$, whence the terminal digit of $u$ is smaller than $k$, which entails
$$g_{k}(h(x))=z(r-1) z(r-1)=g_{k}\left(h\left(g_{k}(x)\right)\right)$$
If $r \leq k$, then
$$g_{k}(h(x))=z(r-1)=g_{k}\left(h\left(g_{k}(x)\right)\right)$$
so that in both cases the equality is true. Thus Lemma 1 is proved.

Lemma 2. Let $k \in\{1, \ldots, 9\}$, let $x$ be a non-empty string and let $n$ be a positive integer. If $h^{n}(x)=\varepsilon$ then $\left(g_{k} \circ h\right)^{n}(x)=\varepsilon$.

Proof of Lemma 2. We proceed by induction on $n$. If $n=1$ we have
$$\varepsilon=h(x)=g_{k}(h(x))=\left(g_{k} \circ h\right)(x)$$
Now consider the step from $n-1$ to $n$ where $n \geq 2$. Let $h^{n}(x)=\varepsilon$ and let $y=h(x)$. Then $h^{n-1}(y)=\varepsilon$ and by the induction hypothesis $\left(g_{k} \circ h\right)^{n-1}(y)=\varepsilon$. In view of Lemma 1,
$$\begin{aligned} & \varepsilon=\left(g_{k} \circ h\right)^{n-2}\left(\left(g_{k} \circ h\right)(y)\right)=\left(g_{k} \circ h\right)^{n-2}\left(g_{k}(h(y))\right) \\ & \quad=\left(g_{k} \circ h\right)^{n-2}\left(g_{k}\left(h\left(g_{k}(y)\right)\right)=\left(g_{k} \circ h\right)^{n-2}\left(g_{k}\left(h\left(g_{k}(h(x))\right)\right)=\left(g_{k} \circ h\right)^{n}(x) .\right.\right. \end{aligned}$$
Thus the induction step is complete and Lemma 2 is proved.

We say that the non-empty string $x$ terminates if $h^{n}(x)=\varepsilon$ for some non-negative integer $n$.

Lemma 3. Let $x=y z r$ where $s(y) \geq k, s(z) \geq k, y$ ends with the digit $k$ and $z$ is possibly empty. If $y$ and $z r$ terminate then also $x$ terminates.

Proof of Lemma 3. Suppose that $y$ and $z r$ terminate. We proceed by induction on $k$. Let $k=0$. Obviously, $h(y w)=y h(w)$ for any non-empty string $w$. Let $h^{n}(z r)=\epsilon$. It follows easily by induction on $m$ that $h^{m}(y z r)=y h^{m}(z r)$ for $m=1, \ldots, n$. Consequently, $h^{n}(y z r)=y$. Since $y$ terminates, also $x=y z r$ terminates.

Now let the assertion be true for all nonnegative integers less than $k$ and let us prove it for $k$ where $k \geq 1$. It turns out that it is sufficient to prove that $y g_{k}(h(z r))$ terminates. Indeed:

Case 1. $r=0$.
Then $h(y z r)=y z=y g_{k}(h(z r))$.

Case 2. $0<r \leq k$.
We have $h(z r)=z(r-1) z(r-1)$ and $g_{k}(h(z r))=z(r-1)$. Then $h(y z r)=y z(r-1) y z(r-1)=y g_{k}(h(z r)) y g_{k}(h(z r))$ and we may apply the induction hypothesis to see that if $y g_{k}(h(z r))$ terminates, then $h(y z r)$ terminates.

Case 3. $r>k$.
Then $h(y z r)=y h(z r)=y g_{k}(h(z r))$.
Note that $y g_{k}(h(z r))$ has the form $y z^{\prime} r^{\prime}$ where $s\left(z^{\prime}\right) \geq k$. By the same arguments it is sufficient to prove that $y g_{k}\left(h\left(z^{\prime} r^{\prime}\right)\right)=y\left(g_{k} \circ h\right)^{2}(z r)$ terminates and, by induction, that $y\left(g_{k} \circ h\right)^{m}(z r)$ terminates for some positive integer $m$. In view of Lemma 2 there is some $m$ such that $(g_{k} \circ h)^{m}(z r)=\epsilon$, so $x=y z r$ terminates if $y$ terminates. Thus Lemma 3 is proved.

Now assume that there is some string $x$ that does not terminate. We choose $x$ minimal. If $x \geq 10$, we can write $x$ in the form $x=y z r$ of Lemma 3 and by this lemma $x$ terminates since $y$ and $z r$ are smaller than $x$. If $x \leq 9$, then $h(x)=(x-1)(x-1)$ and $h(x)$ terminates again by Lemma 3 and the minimal choice of $x$.

We commence by introducing some terminology. Instead of integers, we will consider the set $S$ of all strings consisting of the digits $0,1, \ldots, 9$, including the empty string $\epsilon$. If $\left(a_{1}, a_{2}, \ldots, a_{n}\right)$ is a nonempty string, we let $\rho(a)=a_{n}$ denote the terminal digit of $a$ and $\lambda(a)$ be the string with the last digit removed. We also define $\lambda(\epsilon)=\epsilon$ and denote the set of non-negative integers by $\mathbb{N}_{0}$.

Now let $k \in\{0,1,2, \ldots, 9\}$ denote any digit. We define a function $f_{k}: S \longrightarrow S$ on the set of strings: First, if the terminal digit of $n$ belongs to $\{0,1, \ldots, k\}$, then $f_{k}(n)$ is obtained from $n$ by deleting this terminal digit, i.e $f_{k}(n)=\lambda(n)$. Secondly, if the terminal digit of $n$ belongs to $\{k+1, \ldots, 9\}$, then $f_{k}(n)$ is obtained from $n$ by the process described in the problem. We also define $f_{k}(\epsilon)=\epsilon$. Note that up to the definition for integers $n \leq 1$, the function $f_{0}$ coincides with the function $h$ in the problem, through interpreting integers as digit strings. The argument will be roughly as follows. We begin by introducing a straightforward generalization of our claim about $f_{0}$. Then it will be easy to see that $f_{9}$ has all these stronger properties, which means that is suffices to show for $k \in\{0,1, \ldots, 8\}$ that $f_{k}$ possesses these properties provided that $f_{k+1}$ does.

We continue to use $k$ to denote any digit. The operation $f_{k}$ is said to be separating, if the following holds: Whenever $a$ is an initial segment of $b$, there is some $N \in \mathbb{N}_{0}$ such that $f_{k}^{N}(b)=a$. The following two notions only apply to the case where $f_{k}$ is indeed separating, otherwise they remain undefined. For every $a \in S$ we denote the least $N \in \mathbb{N}_{0}$ for which $f_{k}^{N}(a)=\epsilon$ occurs by $g_{k}(a)$ (because $\epsilon$ is an initial segment of $a$, such an $N$ exists if $f_{k}$ is separating). If for every two strings $a$ and $b$ such that $a$ is a terminal segment of $b$ one has $g_{k}(a) \leq g_{k}(b)$, we say that $f_{k}$ is coherent. In case that $f_{k}$ is separating and coherent we call the digit $k$ seductive.

As $f_{9}(a)=\lambda(a)$ for all $a$, it is obvious that $9$ is seductive. Hence in order to show that $0$ is seductive, which clearly implies the statement of the problem, it suffices to take any $k \in\{0,1, \ldots, 8\}$ such that $k+1$ is seductive and to prove that $k$ has to be seductive as well. Note that in doing so, we have the function $g_{k+1}$ at our disposal. We have to establish two things and we begin with

Step 1. $f_{k}$ is separating.

Before embarking on the proof of this, we record a useful observation which is easily proved by induction on $M$.

Claim 1. For any strings $A, B$ and any positive integer $M$ such that $f_{k}^{M-1}(B) \neq \epsilon$, we have
$$f_{k}^{M}(A k B)=A k f_{k}^{M}(B) .$$

Now we call a pair $(a, b)$ of strings wicked provided that $a$ is an initial segment of $b$, but there is no $N \in \mathbb{N}_{0}$ such that $f_{k}^{N}(b)=a$. We need to show that there are none, so assume that there were such pairs. Choose a wicked pair $(a, b)$ for which $g_{k+1}(b)$ attains its minimal possible value. Obviously $b \neq \epsilon$ for any wicked pair $(a, b)$. Let $z$ denote the terminal digit of $b$. Observe that $a \neq b$, which means that $a$ is also an initial segment of $\lambda(b)$. To facilitate the construction of the eventual contradiction, we prove

Claim 2. There cannot be an $N \in \mathbb{N}_{0}$ such that
$$f_{k}^{N}(b)=\lambda(b)$$

Proof of Claim 2. For suppose that such an $N$ existed. Because $g_{k+1}(\lambda(b))<g_{k+1}(b)$ in view of the coherency of $f_{k+1}$, the pair $(a, \lambda(b))$ is not wicked. But then there is some $N'$ for which $f_{k}^{N'}(\lambda(b))=a$ which entails $f_{k}^{N+N'}(b)=a$, contradiction. Hence Claim 2 is proved.

It follows that $z \leq k$ is impossible, for otherwise $N=1$ violated Claim 2.
Also $z>k+1$ is impossible: Set $B=f_{k}(b)$. Then also $f_{k+1}(b)=B$, but $g_{k+1}(B)<g_{k+1}(b)$ and $a$ is an initial segment of $B$. Thus the pair $(a, B)$ is not wicked. Hence there is some $N \in \mathbb{N}_{0}$ with $a=f_{k}^{N}(B)$, which, however, entails $a=f_{k}^{N+1}(b)$.

We are left with the case $z=k+1$. Let $L$ denote the left part and $R=R^{*}(k+1)$ the right part of $b$. Then we have symbolically
$$f_{k}(b)=L R^{*} k R^{*} k, \quad f_{k}^{2}(b)=L R^{*} k R^{*} \quad \text{and} \quad f_{k+1}(b)=L R^{*} .$$
Using that $R^{*}$ is a terminal segment of $L R^{*}$ and the coherency of $f_{k+1}$, we infer
$$g_{k+1}\left(R^{*}\right) \leq g_{k+1}\left(L R^{*}\right)<g_{k+1}(b)$$
Hence the pair $(\epsilon, R^{*})$ is not wicked, so there is some minimal $M \in \mathbb{N}_{0}$ with $f_{k}^{M}\left(R^{*}\right)=\epsilon$ and by Claim 1 it follows that $f_{k}^{2+M}(b)=L R^{*} k$. Finally, we infer that $\lambda(b)=L R^{*}=f_{k}\left(L R^{*} k\right)= f_{k}^{3+M}(b)$, which yields a contradiction to Claim 2.

This final contradiction establishes that $f_{k}$ is indeed separating.

Step 2. $f_{k}$ is coherent.

To prepare the proof of this, we introduce some further pieces of terminology. A nonempty string $\left(a_{1}, a_{2}, \ldots, a_{n}\right)$ is called a hypostasis, if $a_{n}<a_{i}$ for all $i=1, \ldots, n-1$. Reading an arbitrary string $a$ backwards, we easily find a, possibly empty, sequence $(A_{1}, A_{2}, \ldots, A_{m})$ of hypostases such that $\rho(A_{1}) \leq \rho(A_{2}) \leq \cdots \leq \rho(A_{m})$ and, symbolically, $a=A_{1} A_{2} \ldots A_{m}$. The latter sequence is referred to as the decomposition of $a$. So, for instance, $(20,0,9)$ is the decomposition of $2009$ and the string $50$ is a hypostasis. Next we explain when we say about two strings $a$ and $b$ that $a$ is injectible into $b$. The definition is by induction on the length of $b$. Let $(B_{1}, B_{2}, \ldots, B_{n})$ be the decomposition of $b$ into hypostases. Then $a$ is injectible into $b$ if for the decomposition $(A_{1}, A_{2}, \ldots, A_{m})$ of $a$ there is a strictly increasing function $H:\{1,2, \ldots, m\} \longrightarrow\{1,2, \ldots, n\}$ satisfying
$$\rho(A_{i})=\rho(B_{H(i)}) \text{ for all } i=1, \ldots, m ;$$
$\lambda(A_{i})$ is injectible into $\lambda(B_{H(i)})$ for all $i=1, \ldots, m$.
If one can choose $H$ with $H(m)=n$, then we say that $a$ is strongly injectible into $b$. Obviously, if $a$ is a terminal segment of $b$, then $a$ is strongly injectible into $b$.

Claim 3. If $a$ and $b$ are two nonempty strings such that $a$ is strongly injectible into $b$, then $\lambda(a)$ is injectible into $\lambda(b)$.

Proof of Claim 3. Let $(B_{1}, B_{2}, \ldots, B_{n})$ be the decomposition of $b$ and let $(A_{1}, A_{2}, \ldots, A_{m})$ be the decomposition of $a$. Take a function $H$ exemplifying that $a$ is strongly injectible into $b$. Let $(C_{1}, C_{2}, \ldots, C_{r})$ be the decomposition of $\lambda(A_{m})$ and let $(D_{1}, D_{2}, \ldots, D_{s})$ be the decomposition of $\lambda(B_{n})$. Choose a strictly increasing $H':\{1,2, \ldots, r\} \longrightarrow\{1,2, \ldots s\}$ witnessing that $\lambda(A_{m})$ is injectible into $\lambda(B_{n})$. Clearly, $(A_{1}, A_{2}, \ldots, A_{m-1}, C_{1}, C_{2}, \ldots, C_{r})$ is the decomposition of $\lambda(a)$ and $(B_{1}, B_{2}, \ldots, B_{n-1}, D_{1}, D_{2}, \ldots, D_{s})$ is the decomposition of $\lambda(b)$. Then the function $H'':\{1,2, \ldots, m+r-1\} \longrightarrow\{1,2, \ldots, n+s-1\}$ given by $H''(i)=H(i)$ for $i=1,2, \ldots, m-1$ and $H''(m-1+i)=n-1+H'(i)$ for $i=1,2, \ldots, r$ exemplifies that $\lambda(a)$ is injectible into $\lambda(b)$, which finishes the proof of the claim.

A pair $(a, b)$ of strings is called aggressive if $a$ is injectible into $b$ and nevertheless $g_{k}(a)>g_{k}(b)$. Observe that if $f_{k}$ was incoherent, which we shall assume from now on, then such pairs existed. Now among all aggressive pairs we choose one, say $(a, b)$, for which $g_{k}(b)$ attains its least possible value. Obviously $f_{k}(a)$ cannot be injectible into $f_{k}(b)$, for otherwise the pair $(f_{k}(a), f_{k}(b))$ was aggressive and contradicted our choice of $(a, b)$. Let $(A_{1}, A_{2}, \ldots, A_{m})$ and $(B_{1}, B_{2}, \ldots, B_{n})$ be the decompositions of $a$ and $b$ and take a function $H:\{1,2, \ldots, m\} \longrightarrow\{1,2, \ldots, n\}$ exemplifying that $a$ is indeed injectible into $b$. If we had $H(m)<n$, then $a$ was also injectible into the number $b'$ whose decomposition is $(B_{1}, B_{2}, \ldots, B_{n-1})$ and by separativity of $f_{k}$ we obtained $g_{k}(b')<g_{k}(b)$, whence the pair $(a, b')$ was also aggressive, contrary to the minimality condition imposed on $b$. Therefore $a$ is strongly injectible into $b$. In particular, $a$ and $b$ have a common terminal digit, say $z$. If we had $z \leq k$, then $f_{k}(a)=\lambda(a)$ and $f_{k}(b)=\lambda(b)$, so that by Claim 3, $f_{k}(a)$ was injectible into $f_{k}(b)$, which is a contradiction. Hence, $z \geq k+1$.

Now let $r$ be the minimal element of $\{1,2, \ldots, m\}$ for which $\rho(A_{r})=z$. Then the maximal right part of $a$ consisting of digits $\geq z$ is equal to $R_{a}$, the string whose decomposition is $(A_{r}, A_{r+1}, \ldots, A_{m})$. Then $R_{a}-1$ is a hypostasis and $(A_{1}, \ldots, A_{r-1}, R_{a}-1, R_{a}-1)$ is the decomposition of $f_{k}(a)$. Defining $s$ and $R_{b}$ in a similar fashion with respect to $b$, we see that $(B_{1}, \ldots, B_{s-1}, R_{b}-1, R_{b}-1)$ is the decomposition of $f_{k}(b)$. The definition of injectibility then easily entails that $R_{a}$ is strongly injectible into $R_{b}$. It follows from Claim 3 that $\lambda(R_{a})= \lambda(R_{a}-1)$ is injectible into $\lambda(R_{b})=\lambda(R_{b}-1)$, whence the function $H':\{1,2, \ldots, r+1\} \longrightarrow \{1,2, \ldots, s+1\}$, given by $H'(i)=H(i)$ for $i=1,2, \ldots, r-1$, $H'(r)=s$ and $H'(r+1)=s+1$ exemplifies that $f_{k}(a)$ is injectible into $f_{k}(b)$, which yields a contradiction as before.

This shows that aggressive pairs cannot exist, whence $f_{k}$ is indeed coherent, which finishes the proof of the seductivity of $k$, whereby the problem is finally solved.