IMO 2009 Shortlist C8
For any integer n ≥ 2, we compute the integer h(n) by applying the following procedure to its decimal representation. Le...
Category: Combinatorics
Problem
For any integer n ≥ 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 ≤ r ≤ 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 ≥ 2, iterated application of h produces the integer 1 after finitely many steps.