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 endswith 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. ------------------------------------- It slightly remains of the Goodstein sequence :-), but it should be easier, no trees. I need to understand the second step. So we have a number (whatever)(single digit < r)(digits >= r)r <---------- L ------------><---- R -----> Or (digits >= r)r <----- R ----> Let's try it with something. 3 R 22 RR 2121 RRRR 21202120 2120212 LLLLLLR 21202111 LLLLRRRR 212021102110 21202110211 # comment: the zeroes are actually separators, once a zero appears, it will be always in the L block 21202110211 LLLLLLLLRRR 21202110210210 2120211021021 LLLLLLLLLLLRR 212021102102020 21202110210202 LLLLLLLLLLLLLR 212021102102011 LLLLLLLLLLLLLRR 212021102102011 # comment2 (I should have noticed this earlier): the (-1) subtraction never exceeds one # digit, so the problem is really only about a sequence of digits, not about the entire number at all # it seems that the higher digit we have, the more difficult it is, maybe I could start with proving # for digits up to 1, or 2 212021102102011 LLLLLLLLLLLLLRR 21202110210201010 2120211021020101 LLLLLLLLLLLLLLLR 21202110210201000 21202110210201 LLLLLLLLLLLLLR 212021102102000 212021102102 LLLLLLLLLLLR 2120211021011 LLLLLLLLLLLRR 212021102101010 21202110210101 LLLLLLLLLLLLLR 212021102101000 212021102101 LLLLLLLLLLLR 2120211021000 2120211021 OK, I think it was enough for an idea of how it works I have already eliminated one of the sequence '21', from the string 2120211021021. The other 21 would be eliminated in a similar manner resulting in 2120211 LLLLRRR 2120210210 Again, I eliminate '21' twice 212 LLR 2111 RRRR 21102110 2110211 LLLLRRR 2110210210 Again, eliminate '21' twice 211 RRR 210210 eliminate '21' twice, victory. So, when starting with '3', it works :-) Ideas coming from the experiment: * Try proving for the case when the only digits involved are '0', '1', or '0', '1', '2' * Observe strings S that can be eliminated, and once a string ends with '0S', it can be removed * Issue: What if we will not have the zeroes (at least at the beginning) * Let's hope it will work out somehow. Actually, a zero will appear in at most 9 steps. -- the last digit is decreased by every step (2). But it is untrivial to grasp what is going on in a general case within the 9 steps coming to zero. Let's take a general number with digits up to '5'. A(last1)B(last2)C(last3)D(last4)E5 in other words, A1B2C3D4E5, where E is a sequence consisting of fives only, D only of '5','4', and so on the first 5 steps are A1B2C3D4E5 LLLLLLLLRR A1B2C3D4E4E4 LLLLLLRRRRRR A1B2C3D4E4E3D4E4E3 LLLLRRRRRRRRRRRRRR A1B2C3D4E4E3D4E4E2C3D4E4E3D4E4E2 LLRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR A1B2C3D4E4E3D4E4E2C3D4E4E3D4E4E1B2C3D4E4E3D4E4E2C3D4E4E3D4E4E1 RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR A1B2C3D4E4E3D4E4E2C3D4E4E3D4E4E1B2C3D4E4E3D4E4E2C3D4E4E3D4E4E0A1B2C3D4E4E3D4E4E2C3D4E4E3D4E4E1B2C3D4E4E3D4E4E2C3D4E4E3D4E4E0 And just now, we have a zero, so we can handle the two copies of A1B2C3D4E4E3D4E4E2C3D4E4E3D4E4E1B2C3D4E4E3D4E4E2C3D4E4E3D4E4E0 separately, so in fact, the last step can be seen as A1B2C3D4E4E3D4E4E2C3D4E4E3D4E4E1B2C3D4E4E3D4E4E2C3D4E4E3D4E4E1 -> A1B2C3D4E4E3D4E4E2C3D4E4E3D4E4E1B2C3D4E4E3D4E4E2C3D4E4E3D4E4E Hm... I am at the same setup, but without any zero, with ones acting as zeroes. This solution should be formalizable (if handled carefully) It corresponds to the idea that we limit ourselves to the digits 0..d just that the digits 1..9 play the role of digits 0..8 Proof: * We prove by induction on 'd' that the theorem is true, if the given number contains only digits 0..d * If d=0, it is trivially satisfied (it suffices to use the step (1)) * Induction step, assume d > 0. * Split the input string by all the zeroes. * Take the last string S from the split. * let T = map (-1) S * by induction assumption, we find a sequence of steps (1) and (2) that eliminates the string T * From this, we construct a sequence of steps which eliminates the string S * Any operation (2) on T corresponds to the same operation (2) on S in other words, the operation (2) commutes with (map (-1)) * Any operation (1) on T adds a zero to S and duplicates it. * It is kind of obvious how it helps but I am not sure how to formally write it. * Because elimination of the first copy can be used for elimination of the second copy. * This way: induction by the number of steps on T :-) * Let's write the induction step once again ------------ * First, we prove claim: every string S containing numbers 1..d can be eliminated * By induction assumption, we know that T = map (-1) S can be aliminated * Prove the claim by induction on the number of steps in the elimination process of T * First step of induction is trivial: * if T can be eliminated in 0 steps, T is empty, so S is empty as well, so S can be eliminated in 0 steps * Induction step: * Take the first step of te elimination process of T, case analysis by its type: * Action (1) * Let S' and T' be S and T without their last digits 1,0 repectively. * T' can be eliminated in 1 less steps than T, therefore by induction assumption, S' can be eliminated * If we follow the procedure on S, we must use the step (2) getting (S')0(S')0 * Then we apply the step (2), getting (S')0(S') * Then we eliminate S' by induction assumption (S')0 * Apply once again, and S is eliminated. * Action (2) * Let S', T' be the strings S, T after applying the step (2) once. * By definition of the step (2), T' = map (-1) S' * T' can be eliminated in 1 less steps than T, therefore S' can be eliminated by induction assumption * Therefore, S can be eliminated * Claim proved! * Using the claim, it is apparent that every string containing numbers 0..d can be eliminated since 0 serves only as a separator in the process. QED