Interesting separate question: Are there any good estimates on the number of applications of $h$ to reach $1$ from the initial sequence $19$ (or more generally $1k$, assuming we extend the procedure to sequences instead of digits)?

I have a solution that seems to imply that this problem is too easy for C8, so it's probably wrong...

pythag011 wrote: I have a solution that seems to imply that this problem is too easy for C8, so it's probably wrong...

I think your idea is ok, though I have tried to make it work for a while, with no luck; the problem starts when all your digits are relatively large, I have found it quite hard to formulate adequately your idea into an actual proof. I have however a different proof:

An extension to this problem - how many steps does it actually take to get to "1"? If you write a program to brute force it, you will get $7$ steps for "2" and $206$ steps for "3". With some DP I get $282010037162402640940473134964124459341$ steps for "4". How many steps does it take for "5" or higher?

April wrote: For any integer $n\geq 2$, we compute the integer $h(n)$ by applying the following procedure to its decimal representation. Let $r$ be the rightmost digit of $n$. If $r=0$, then the decimal representation of $h(n)$ results from the decimal representation of $n$ by removing this rightmost digit $0$. If $1\leq r \leq 9$ we split the decimal representation of $n$ into a maximal right part $R$ that solely consists of digits not less than $r$ and into a left part $L$ that either is empty or ends with a digit strictly smaller than $r$. Then the decimal representation of $h(n)$ consists of the decimal representation of $L$, followed by two copies of the decimal representation of $R-1$. For instance, for the number $17,151,345,543$, we will have $L=17,151$, $R=345,543$ and $h(n)=17,151,345,542,345,542$. Prove that, starting with an arbitrary integer $n\geq 2$, iterated application of $h$ produces the integer $1$ after finitely many steps. Proposed by Gerhard Woeginger, Austria The underlined: Does this mean that an iterated application of $h$ will soon produce the number $1$ or a number with the digit $1$?

Unambiguously the former.

Of course. It just looked too unbeliveable and surprising that iterated applications of $h$ could produce $1$. I guess it doesn't look as surprising now since one only has to prove that the process will terminate.

daniel73 wrote:

What is the motivation for $\ell(n)$?

MathPanda1 wrote: daniel73 wrote:

What is the motivation for $\ell(n)$? A typical method to solve this kind of problems. Whenever you have a problem where you iterate from one state to the next (in this case the states would be $n,h(n),h(h(n)),\dots$), you find a way to assign a non-negative integer to each state (in this case $\ell(n)$) so that in each iteration, the integer decreases. Regardless of how large the initial integer is, if it must always be non-negative, and if it always decreases, then necessarily after a finite number of steps (at most equal to the initial integer, and though it may be very large, as in this problem), you would "reach $0$", ie the process would end after a finite number of steps. Since passing through the state "$1$" is necessary for the process to finish, then $1$ will be reached after a finite number of steps. There are many Olympiad problems solvable through this method, although my favorite of this kind is still problem 3 in IMO 1986.

pythag011 wrote: I have a solution that seems to imply that this problem is too easy for C8, so it's probably wrong...

My solution is almost the same, besides what you said can be written in a very fast and direct way if we exploit induction on the maximal digit in the decimal representation of $n$. Infact when you say that we can delete the last digit if it is $1$, then, noting that $1$ behaves as a $0$, we can decrease by $1$ all digits of the initial number $n$ (we supposed $WLOG$ it didn't have any $0$s), so now we can apply the induction hypotesis. The basic case of induction is trivial (we can even consider $n=0$ as the basic case, it suffices to see that the thesis of the problem is equivalent to show that the iterated application of $h$ produces the integer $0$).

Abuse of Notation. We will treat $r,L,R$ as functions of $n$. Thus, the values of $r,L,R$ always depend on the value of $n$. Let $\mathbb{Z}_2$ denote the set of integers that are at least 2, and let $\mathbb{Z}_1$ denote the set of integers that are at least 1. For any function $f : \mathbb{Z}_2 \rightarrow \mathbb{Z}_1$, we will call $f$ a tank if, for all $n \ge 2$, iterated application of $f$ produces the integer $1$ after finitely many steps. For $n \ge 2$, we will call $n$ a bomb if iterated application of $f$ on $n$ does not produce the integer $1$ in finitely many steps. It's obvious that $h$ is a function from $\mathbb{Z}_2$ to $\mathbb{Z}_1$. Our goal is to show that $h$ is a tank. To do so, we will define the following functions $h_i : \mathbb{Z}_2 \rightarrow \mathbb{Z}_1$ for $0 \le i \le 9$: If $r = 0$, then the decimal representation of $h_i(n)$ results from the decimal representation of $n$ by removing this rightmost digit $0$. If $1 \le r \le i$, then the decimal representation of $h_i(n)$ results from the decimal representation of $n$ by replacing the rightmost digit $r$ with the digit $r-1$. If $r > i$, the decimal representation of $h_i(n)$ consists of the decimal representation of $L$, followed by two copies of the decimal representation of $R-1$. It's clear that $h = h_0$. The following Lemma constitutes the core of this problem: Lemma 1. If $h_{i+1}$ is a tank, then $h_i$ is a tank. Proof. Note that $h_{i+1}(n)$ and $h_i(n)$ agree unless $r = i+1$, in which case $h_{i+1}(n)$ consists of the decimal representation of $L$ followed by the decimal representation of $R-1$, and $h_i(n)$ consists of the decimal representation of $L$ followed by two copies of the decimal representation of $R-1$. In a number $n$, let $d$ be one of its digits. Define $d$ to be a block if $0 \le d \le i$. Note that a block can never be part of $R$ under either $h_{i+1}$ or $h_i$. This means that the digits to the left of the block will not change until the block becomes the rightmost digit. Define the left part $A$ such that it consists of the digits strictly to the left of the block and the right part $B$ such that it consists of the digits strictly to the right of the block. Then applying either $h_{i+1}$ or $h_i$ to $n$ will yield the same result as $A$ prepended to the result of applying (respectively) $h_{i+1}$ or $h_i$ to $B$. Now assume that $h_{i+1}$ is a tank. We will show that $h_i$ is a tank; i.e. there does not exist $n$ such that $n$ is a bomb under $h_i$. We will prove that such $n$ does not exist by induction on $k$, the number of times $r = i+1$ happens while iteratively applying $h_{i+1}$ to $n$. (Since $h_{i+1}$ is a tank, $k$ is finite.) Our inductive hypothesis will be that, for any given $k$, $n$ is not a bomb under $h_i$. Our base case is $k = 0$. This implies that $h_{i+1}$ and $h_i$ always agree when iteratively applied to $n$, so $n$ is not a bomb under $h_i$. For the inductive step, suppose that the inductive hypothesis is true for $k = s$, where $s \ge 0$. We will prove the inductive hypothesis for $k = s+1$. Let $n',L',R'$ be the values of $n,L,R$ respectively at the earliest point where $r = i+1$ happens (so the units digit of $n'$ is $i + 1$). Note that the units digit of $L'$ is a block, or $L'$ is empty. Additionally, the units digit of $R'-1$ is a block. Note that $h_{i+1}(n')$ consists of $L'$ followed by $R'-1$, while $h_i(n')$ consists of $L'$ followed by $R'-1$ followed by $R' - 1$. By the inductive hypothesis, $h_{i+1}(n')$ is not a bomb under $h_i$. By the aforementioned behavior of blocks, under $h_i$, $R'-1$ will eventually disappear, and then $L'$ will eventually disappear. But this means that $h_i(n')$ is not a bomb under $h_i$, so $n$ is not a bomb under $h_i$ as desired. This completes the induction. $\blacksquare$ And now we are done, since Lemma 2. $h_9$ is a tank. Proof. Note that $h_9(n) < n$ for all $n$. This immediately implies that iterated application of $h_9$ will produce the integer $1$ after finitely many steps, as desired. $\blacksquare$

Call a number terminating if iterated application of $h$ produces $1$ after finitely many steps. First, some easy observations: Lemma 1. If $M$ and $N$ are terminating, then the concatenation $M0N$ is also terminating. Proof. Let $N = n_1 \rightarrow n_2 \rightarrow n_3 \rightarrow \dots \rightarrow n_k = 1$ be the sequence of iterations of $h$ applied to $N$ that result in $1$. Then it is easy to see that $M0$ must be part of the $L$ whenever the rightmost digit of $M0n_i$ is at least $1$, and removing a trailing zero from $M0n_i$ does not affect the $M0$ part. Therefore we have $M0N = M0n_1 \rightarrow M0n_2 \rightarrow M0n_3 \rightarrow \dots \rightarrow M0n_k = M0$ as well. Then $M0 \rightarrow M \rightarrow \dots \rightarrow 1$ since $M$ is terminating, so $M0N$ is terminating as well. Therefore, by induction, we may partition any $N$ into groups separated by zeroes and to prove $N$ is terminating, it suffices to prove that each group is terminating. Hence, it suffices to prove that numbers containing no zero are terminating. Call such numbers buoyant. Lemma 2. If $L$ is buoyant and terminating, then so is $L1$. Proof. $L1 \rightarrow L0L0 \rightarrow L0L$. But $L$ is terminating, so $L0L$ and $L1$ are also terminating. For a buoyant $N$, define $d(N)$ to be the number (possibly with leading $0$'s) formed by subtracting $1$ from each digit of the decimal representation of $N$. (For instance, $d(12345) = 01234$.) The argument of Lemma 1 shows that the leading zeroes are irrelevant when considering whether a number terminates. Lemma 3. If $N$ is buoyant and $d(N)$ is terminating, then $N$ is also terminating. Proof. Let $d(N) = d(n_1) \rightarrow d(n_2) \rightarrow d(n_3) \rightarrow \dots d(n_k) = d(111\dots 12) = 000\dots01$ be the sequence of iterations applied to $d(N)$ that result in $1$, keeping leading zeroes. (We add $1$ to each digit in the sequence to form the $n_i$. This is allowed since the largest digit in $d(n_i)$ is a non-increasing sequence, hence at most $8$.) We claim that $n_i$ is terminating by reverse induction. Base case is that $n_k = 111\dots 12$ is terminating. This is clear since $11\dots 12 \rightarrow 11\dots11$, the last of which is terminating by Lemma 2. Inductive step: Suppose $n_{i+1}$ is terminating. Consider $d(n_i) \rightarrow d(n_{i+1})$. If the last digit of $d(n_i)$ is $0$, then the last digit of $n_i$ is $1$. Also $d(n_i) = d(n_{i+1})0$, so $n_i = n_{i+1}1$. Thus $n_i = n_{i+1}1$, which is terminating by Lemma 2. If the last digit of $d(n_i)$ is at least $1$, then the last digit of $n_i$ is at least $2$ and therefore $n_i \rightarrow n_{i+1}$, which means both are terminating. This completes the inductive step and proves Lemma 3. We will prove by induction on $r$ that any number with digits at most $r$ is terminating. The base case is $r = 1$, which is a result of Lemmas 1 and 2. Inductive step: Suppose numbers with digits at most $r-1$ are terminating. We will prove $N$ with digits at most $r$ is terminating. First, it clearly suffices to show this result for buoyant $N$. Now, consider $d(N)$. If $d(N) = 00\dots0$, then $N$ consists of only $1$'s, which is terminating by Lemma 2. Otherwise, the value of $d(N) > 0$ and it has digits at most $r-1$, so by the inductive hypothesis, it is terminating. Thus, by Lemma 3, $N$ is terminating as well, completing the inductive step and thus the proof of the main result. Notice that our method can be used to prove the result for all bases, instead of base 10.

Suppose a number is of the form $A=A_10A_20\ldots 0A_k$, where $A_i$ are contiguous sequences of nonzero digits. Note that $h$ only affects $A_k$ as long as the $0$ before it isn't deleted. Afterwards, it only affects $A_{k-1}$ and so forth. So, as $h$ affects only the last $A_i$ at any given time, $A$ goes to 1 if $A_1,\ldots,A_k$ all go to $0$. So, we only need to prove this question for sequences of nonzero digits. Now, the only way to get from a sequence of nonzero digits to one with a $0$ is if we go from $B=A1\to A0A0\to A0A$. However, by similar logic as above, $B$ goes to 1 if $A$ does. So, define a new function $g(n)$ on $n$ with nonzero digits such that $g(n)=f(n)$ if $n\pmod{10}>1$, and if it has a trailing $1$, we just delete it. We have reduced the question to showing that iterated applications of $g$ eventually completely remove the number. In fact, this is the same question as the initial one, except we now only have 9 digits. So, we use the same logic to get it to only 8 digits, and so forth, until we reduce the question to: Define a function $f$ to be removing the last digit from a sequence of $9$s. Show that repeated application of fs eventually turns a sequence of $9$s into nothing. Of course, this is trivial.

Solved with YA, Gogobao, and The_Turtle We claim in fact that we may repeat $R-1$ an arbitrary number of times each step, possibly changing the number of times (this means that it could increase very rapidly; for example, we could repeat it $2^i$ times where $i$ is the index in the sequence). Additionally, the digits can be any natural numbers (including 0).