Q15 Matemática  (IMO Shortlist 2009)

Para qualquer inteiro $n\ge 2$, calculamos o inteiro $h(n)$ aplicando o seguinte procedimento à sua representação decimal. Seja $r$ o dígito mais à direita de $n$. Se $r=0$, então a representação decimal de $h(n)$ resulta da representação decimal de $n$ removendo este dígito $0$ mais à direita. Se $1\le r\le 9$ dividimos a representação decimal de $n$ em uma parte máxima direita $R$ que consiste apenas em dígitos não inferiores a $r$ e em uma parte esquerda $L$ que é vazia ou termina com um dígito estritamente menor que $r$. Então a representação decimal de $h(n)$ consiste na representação decimal de $L$, seguida por duas cópias da representação decimal de $R-1$. Por exemplo, para o número $\mathrm{17.151.345.543}$, teremos $L=17.151$, $R=345.543$ e $h(n)=\mathrm{17.151.345.542.345.542}$. Prove que, começando com um inteiro arbitrário $n\ge 2$, a aplicação iterada de $h$ produz o inteiro $1$ após um número finito de passos. Proposto por Gerhard Woeginger, Áustria