IMO Problem Shortlist

We identify integers $n\ge 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,\dots ,f_9$ that map some strings into integers for $k=9,8,\dots ,1,0$. The function $f_9$ is only defined on strings $x$ (including the empty string $\epsilon$) that entirely consist of nines. If $x$ consists of $m$ nines, then $f_9(x)=m+1$, $m=0,1,\dots$. For $k\le 8$, the domain of $f_k(x)$ is the set of all strings consisting only of digits that are $\ge k$. We write $x$ in the form $x_{0}k{x}_{1}k{x}_{2}k\dots x_{m-1}k{x}_m$ where the strings $x_s$ only consist of digits $\ge k+1$. Note that some of these strings might equal the empty string $\epsilon$ 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,\dots ,k-1$. In particular, $f_i(\epsilon )=4^{9-i}$ for all $i=0,1,\dots ,9$. Moreover, by induction on $k=9,8,\dots ,0$ it follows easily: Fact 2. If the nonempty string $x$ does not contain digits smaller than $k$, then $f_i(x)>f_i(\epsilon )$ for all $i=0,\dots ,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, $\epsilon$ can only be reached via the strings $1\to 00\to 0\to \epsilon$. 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\dots 0x_{m-1}0\epsilon$ where the $x_i$ do not contain the digit $0$. Then $h(n)=x_{0}0\dots 0x_{m-1}$ and $f_0(n)-f_0(h(n))=f_0(\epsilon )>0$. So let the last digit $r$ of $n$ be at least $1$. Let $L=yk$ and $R=zr$ be the corresponding left and right parts where $y$ is some string, $k\le r-1$ and the string $z$ consists only of digits not less than $r$. Then $n=ykzr$ and $h(n)=ykz(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)\ge k$. Then $$f_k(n)-f_k(h(n))=f_k(zr)-f_k(z(r-1)z(r-1)).$$ In view of Fact 1 this difference is positive if and only if $$f_{r-1}(zr)-f_{r-1}(z(r-1)z(r-1))>0$$ We have, using Fact 2, $$f_{r-1}(zr)=4^{f_r(zr)}=4^{f_r(z)+4^{f_{r+1}(\epsilon )}}\ge 4\cdot 4^{f_r(z)}>4^{f_r(z)}+4^{f_r(z)}+4^{f_r(\epsilon )}=f_{r-1}(z(r-1)z(r-1)).$$ Here we use the additional definition $f_{10}(\epsilon )=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)\le k$. We prove by induction on $d(y)=k,k-1,\dots ,0$ that $f_i(n)-f_i(h(n))>0$ for all $i=0,\dots ,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 $utv$ where $v$ does not contain digits $\le t$. Then, in view of the induction hypothesis, $$f_t(n)-f_t(h(n))=f_t(vkzr)-f_t(vkz(r-1)z(r-1))=4^{f_{t+1}(vkzr)}-4^{f_{t+1}(vkz(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$.

---

Alternative solution.

We identify integers $n\ge 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, $\epsilon$, 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(\epsilon )=\infty$. We define nine functions $g_1,\dots ,g_9$ as follows: Let $k\in \{1,\dots ,9\}$ and let $x$ be a string. If $x=\epsilon$ then $g_k(x)=\epsilon$. Otherwise, write $x$ in the form $x=yzr$ where $y$ is either the empty string or ends with a digit smaller than $k$, $s(z)\ge k$ and $r$ is the rightmost digit of $x$. Then $g_k(x)=zr$.

Lemma 1. We have $g_k\circ h=g_k\circ h\circ g_k$ for all $k=1,\dots ,9$.

Proof of Lemma 1. Let $x=yzr$ be as in the definition of $g_k$. If $y=\epsilon$, then $g_k(x)=x$, whence $$g_k(h(x))=g_k(h\left(g_k(x)\right)$$ So let $y\ne \epsilon$.

Case 1. $z$ contains a digit smaller than $r$. Let $z=uav$ where $a<r$ and $s(v)\ge r$. Then $$h(x)=\{\begin{array}{ll}yuav& \text{if }r=0\\ yuav(r-1)v(r-1)& \text{if }r>0\end{array}$$ and $$h\left(g_k(x)\right)=h(zr)=h(uavr)=\{\begin{array}{ll}uav& \text{if }r=0\\ uav(r-1)v(r-1)& \text{if }r>0\end{array}$$ 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=uv$ where $u$ is either the empty string or ends with a digit smaller than $r$ and $s(v)\ge r$. We have $$h(x)=\{\begin{array}{ll}uvz& \text{if }r=0\\ uvz(r-1)vz(r-1)& \text{if }r>0\end{array}$$ and $$h\left(g_k(x)\right)=h(zr)=\{\begin{array}{ll}z& \text{if }r=0\\ z(r-1)z(r-1)& \text{if }r>0\end{array}$$ 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=\epsilon$, 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\le 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,\dots ,9\}$, let $x$ be a non-empty string and let $n$ be a positive integer. If $h^n(x)=\epsilon$ then ${\left(g_k\circ h\right)}^n(x)=\epsilon$.

Proof of Lemma 2. We proceed by induction on $n$. If $n=1$ we have $$\epsilon =h(x)=g_k(h(x))=\left(g_k\circ h\right)(x)$$ Now consider the step from $n-1$ to $n$ where $n\ge 2$. Let $h^n(x)=\epsilon$ and let $y=h(x)$. Then $h^{n-1}(y)=\epsilon$ and by the induction hypothesis ${\left(g_k\circ h\right)}^{n-1}(y)=\epsilon$. In view of Lemma 1, $$\begin{array}{rl}& \epsilon ={\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)\\ & ={\left(g_k\circ h\right)}^{n-2}(g_k\left(h\left(g_k(y)\right)\right)={\left(g_k\circ h\right)}^{n-2}(g_k\left(h\left(g_k(h(x))\right)\right)={\left(g_k\circ h\right)}^n(x).\end{array}$$ Thus the induction step is complete and Lemma 2 is proved.

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

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

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

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

Case 1. $r=0$. Then $h(yzr)=yz=y{g}_k(h(zr))$.

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

Case 3. $r>k$. Then $h(yzr)=yh(zr)=y{g}_k(h(zr))$. Note that $y{g}_k(h(zr))$ has the form $y{z}^{\prime }{r}^{\prime }$ where $s\left(z^{\prime }\right)\ge 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(zr)$ terminates and, by induction, that $y{\left(g_k\circ h\right)}^m(zr)$ terminates for some positive integer $m$. In view of Lemma 2 there is some $m$ such that $(g_k\circ h{)}^m(zr)=ϵ$, so $x=yzr$ 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\ge 10$, we can write $x$ in the form $x=yzr$ of Lemma 3 and by this lemma $x$ terminates since $y$ and $zr$ are smaller than $x$. If $x\le 9$, then $h(x)=(x-1)(x-1)$ and $h(x)$ terminates again by Lemma 3 and the minimal choice of $x$.

---

Alternative solution.

We commence by introducing some terminology. Instead of integers, we will consider the set $S$ of all strings consisting of the digits $0,1,\dots ,9$, including the empty string $ϵ$. If $\left(a_1,a_2,\dots ,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 (ϵ)=ϵ$ and denote the set of non-negative integers by ${\mathbb{N}}_0$.

Now let $k\in \{0,1,2,\dots ,9\}$ denote any digit. We define a function $f_k:S⟶S$ on the set of strings: First, if the terminal digit of $n$ belongs to $\{0,1,\dots ,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,\dots ,9\}$, then $f_k(n)$ is obtained from $n$ by the process described in the problem. We also define $f_k(ϵ)=ϵ$. Note that up to the definition for integers $n\le 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,\dots ,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)=ϵ$ occurs by $g_k(a)$ (because $ϵ$ 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)\le 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,\dots ,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)\ne ϵ$, we have $$f_k^M(AkB)=Ak{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\ne ϵ$ for any wicked pair $(a,b)$. Let $z$ denote the terminal digit of $b$. Observe that $a\ne 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^{\prime }$ for which $f_k^{N^{\prime }}(\lambda (b))=a$ which entails $f_k^{N+N^{\prime }}(b)=a$, contradiction. Hence Claim 2 is proved.

It follows that $z\le 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^{\ast }(k+1)$ the right part of $b$. Then we have symbolically $$f_k(b)=L{R}^{\ast }k{R}^{\ast }k,f_k^2(b)=L{R}^{\ast }k{R}^{\ast }\text{and}{f}_{k+1}(b)=L{R}^{\ast }.$$ Using that $R^{\ast }$ is a terminal segment of $L{R}^{\ast }$ and the coherency of $f_{k+1}$, we infer $$g_{k+1}\left(R^{\ast }\right)\le g_{k+1}\left(L{R}^{\ast }\right)<g_{k+1}(b)$$ Hence the pair $(ϵ,R^{\ast })$ is not wicked, so there is some minimal $M\in {\mathbb{N}}_0$ with $f_k^M\left(R^{\ast }\right)=ϵ$ and by Claim 1 it follows that $f_k^{2+M}(b)=L{R}^{\ast }k$. Finally, we infer that $\lambda (b)=L{R}^{\ast }=f_k\left(L{R}^{\ast }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,\dots ,a_n\right)$ is called a hypostasis, if $a_n<a_i$ for all $i=1,\dots ,n-1$. Reading an arbitrary string $a$ backwards, we easily find a, possibly empty, sequence $(A_1,A_2,\dots ,A_m)$ of hypostases such that $\rho (A_1)\le \rho (A_2)\le \cdots \le \rho (A_m)$ and, symbolically, $a=A_1{A}_2\dots 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,\dots ,B_n)$ be the decomposition of $b$ into hypostases. Then $a$ is injectible into $b$ if for the decomposition $(A_1,A_2,\dots ,A_m)$ of $a$ there is a strictly increasing function $H:\{1,2,\dots ,m\}⟶\{1,2,\dots ,n\}$ satisfying $$\rho (A_i)=\rho (B_{H(i)})\text{ for all }i=1,\dots ,m;$$ $\lambda (A_i)$ is injectible into $\lambda (B_{H(i)})$ for all $i=1,\dots ,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,\dots ,B_n)$ be the decomposition of $b$ and let $(A_1,A_2,\dots ,A_m)$ be the decomposition of $a$. Take a function $H$ exemplifying that $a$ is strongly injectible into $b$. Let $(C_1,C_2,\dots ,C_r)$ be the decomposition of $\lambda (A_m)$ and let $(D_1,D_2,\dots ,D_s)$ be the decomposition of $\lambda (B_n)$. Choose a strictly increasing $H^{\prime }:\{1,2,\dots ,r\}⟶\{1,2,\dots s\}$ witnessing that $\lambda (A_m)$ is injectible into $\lambda (B_n)$. Clearly, $(A_1,A_2,\dots ,A_{m-1},C_1,C_2,\dots ,C_r)$ is the decomposition of $\lambda (a)$ and $(B_1,B_2,\dots ,B_{n-1},D_1,D_2,\dots ,D_s)$ is the decomposition of $\lambda (b)$. Then the function $H^{\prime \prime }:\{1,2,\dots ,m+r-1\}⟶\{1,2,\dots ,n+s-1\}$ given by $H^{\prime \prime }(i)=H(i)$ for $i=1,2,\dots ,m-1$ and $H^{\prime \prime }(m-1+i)=n-1+H^{\prime }(i)$ for $i=1,2,\dots ,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,\dots ,A_m)$ and $(B_1,B_2,\dots ,B_n)$ be the decompositions of $a$ and $b$ and take a function $H:\{1,2,\dots ,m\}⟶\{1,2,\dots ,n\}$ exemplifying that $a$ is indeed injectible into $b$. If we had $H(m)<n$, then $a$ was also injectible into the number $b^{\prime }$ whose decomposition is $(B_1,B_2,\dots ,B_{n-1})$ and by separativity of $f_k$ we obtained $g_k(b^{\prime })<g_k(b)$, whence the pair $(a,b^{\prime })$ 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\le 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\ge k+1$.

Now let $r$ be the minimal element of $\{1,2,\dots ,m\}$ for which $\rho (A_r)=z$. Then the maximal right part of $a$ consisting of digits $\ge z$ is equal to $R_a$, the string whose decomposition is $(A_r,A_{r+1},\dots ,A_m)$. Then $R_a-1$ is a hypostasis and $(A_1,\dots ,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,\dots ,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^{\prime }:\{1,2,\dots ,r+1\}⟶\{1,2,\dots ,s+1\}$, given by $H^{\prime }(i)=H(i)$ for $i=1,2,\dots ,r-1$, $H^{\prime }(r)=s$ and $H^{\prime }(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.