2009 IMO Shortlist C8

AUT 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$. (1) If $r=0$, then the decimal representation of $h(n)$ results from the decimal representation of $n$ by removing this rightmost digit 0 . (2) 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 $n=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.

AUT 对于任何整数 $n \geq 2$，我们通过将以下过程应用于其十进制表示来计算整数 $h(n)$。令 $r$ 为 $n$ 最右边的数字。 (1) 如果 $r=0$，则 $h(n)$ 的十进制表示形式是通过删除最右边的数字 0 从 $n$ 的十进制表示形式得出的。 (2) 如果 $1 \leq r \leq 9$，我们将 $n$ 的十进制表示形式拆分为仅由不小于 $r$ 的数字组成的最大右侧部分 $R$ 和左侧部分 $L$，该部分为空或以严格小于 $r$ 的数字结尾。那么 $h(n)$ 的十进制表示形式由 $L$ 的十进制表示形式组成，后跟 $R-1$ 的十进制表示形式的两个副本。例如，对于数字 $n=17,151,345,543$，我们将有 $L=17,151、R=345,543$ 和 $h(n)=17,151,345,542,345,542$。证明，从任意整数 $n \geq 2$ 开始，迭代应用 $h$ 经过有限多个步骤后会产生整数 1。