I Thought This Could Continue Forever - Part 2

999981, ... , 1000018 is a lucky chain of length 38.

Now, for any positive integer $n$ , let $S(n)$ be the set $\{10n, ... , 10n+9\}$ , and note that $S(n)$ can only be contained in a lucky chain if the digit sum of $n$ is $\equiv 1 \mod 11$ . But if a lucky chain of length 39 (or more) exists, it must contain $S(n) \cup S(n+1) \cup S(n+2)$ for some positive integer $n$ . This implies that $n, n+1, n+2$ each have digit sum $\equiv 1 \mod 11$ , which in turn implies that the last digits of $n, n+1$ are both 9, a contradiction.

I would really love a good solution for this.

I tried it this way:

If we start from '1', we can reach only up to 28, before the sum of digits is a multiple of 11 Now, if we take any 2 successive numbers whose digit sum is a multiple of 11, the difference would be 9 Comparing the highest such 2 digit number and the least 3 digit number, viz. 92 and 119, the difference is 27, so 26 numbers in between

This is when I realized, the largest sequence will be formed between the highest n-digit number and the least (n+1)-digit number, whose digit sum is a multiple of 11

Now, if we test few highest n-digit numbers:

• 92
• 994
• 9996
• 99998
• 99980

If, we observe the 5th number, this has the last two digits as 80

Now, the least (n+1)-digit number whose digit sum is a multiple of 11 are always of the form:

• 119
• 1019
• 10019
• 100019
• 1000019

As, the last two digits are always same, this will not play a deciding factor.

So the maximum difference is for 1000019 - 999980 = 39

As, the difference is 39, there must be $\boxed{38}$ numbers in between

PS: I cross checked each of the highest n-digit numbers, and found a repetitive pattern

• 92
• 9 94
• 99 96
• 999 98
• 9999 80
• 99999 91
• 999999 93
• 9999999 95
• 99999999 97
• 999999999 99
• 9999999999 90
• 99999999999 92

The last two digits form a cycle ...

Here's how I sort of confidently arrived at the correct answer.

We focus on the main property of the numbers in the sequence: Consecutive numbers.

Denote $k(n)$ the sum of the digits of $n$ excluding its units digit in $\pmod {11}$ .

When a sequence contains all $10$ consecutive numbers with the same tens digit:

i.e. in $\pmod {11}: k(i)+0,k(i)+1,...,k(i)+9$ where $i$ is the first number.

Since none of the numbers is $\equiv 0 \pmod {11}$ , therefore it must be ture that $k(i)\equiv 1$ . If we continue the sequence, thereby increasing the tens digits by $1$ (assuming that the tens digits is not $9$ ), then $k(i+10)\equiv 2$ , where $i+10$ is the first number with the new tens digit. This means the sequence can only go as far as to $i+18$ since $k(i+10)+9\equiv 2+11\equiv 0$ . Together we conclude that for a sequence of numbers that has the same hundreds digit, the longest length of such sequence is $10+9=19$ .

Note that to lengthen our list to maximum, we could combine two sequences of numbers with two different hundreds digits. Base on our results from above, our maximum should be $19\times 2=\boxed {38}$ , now we just have to find a satisfying sequence, which is not hard to do using our argument above.