Problem of the Month
Solution to Problem 1: October 2023

Before presenting solutions to the various parts of this question, we present a few general facts that will be used throughout the solutions. As well, we will often denote a list of integers enclosed in brackets. For example, we might write $[1,2,3,4,5]$ instead of $1,2,3,4,5$. This is to emphasize when we want to think of a list is a single object to which we can refer.

Fact 1: If $n$ is a positive integer with units digit different from $9$, then $D(n+1)=D(n)+1$.

Fact 2: Suppose that $L=[n,n+1,n+2,\dots ,n+k]$ is a list of consecutive non-negative integers. If none of $n+1,n+2,\dots ,n+k$ is a multiple of $10$, then the integers $D(n),D(n+1),\dots ,D(n+k)$ are consecutive.

Fact 3: Suppose $m$ is an integer with $m>1$ and that $[a,a+1,a+2,\dots ,a+(m-2)]$ is a list of $m-1$ consecutive integers with the property that no integer in the list is a multiple of $m$. Then the remainder after $a$ is divided by $m$ is $1$ and the remainder after $a+m-2$ is divided by $m$ is $m-1$.

For a positive integer $n$ with units digit $d$, we say that $n$ has $k$ trailing $d$s if the rightmost $k$ digits of $n$ are $d$ but the rightmost $k+1$ digits are not equal to $d$. For example, the integer $123$ has one trailing $3$, $45000$ has three trailing $0$s, and $29199$ has two trailing $9$s.

By Fact 1, it is "usually" easy to predict $D(n+1)$ from $D(n)$ since if the units digit of $n$ is not $9$, then $D(n+1)=D(n)+1$. However, if the units digit of $n$ is $9$, then adding $1$ causes a carry to happen, so the digit sum can go down. For example, the digit sum of $2499$ is $D(2499)=2+4+9+9=24$, but the digit sum of $2499+1=2500$ is $D(2500)=2+5+0+0=7$. Fact 4 establishes a relationship between $D(n)$ and $D(n+1)$ when $n$ has a units digit of $9$.

Fact 4: Suppose $n$ is a positive integer with $t$ trailing $9$s. Then $D(n+1)-D(n)=1-9t$.

Remark: We will repeatedly use the observation that if $L=[a,a+1,a+2,\dots ,a+k]$ is an $m$-list for some $m$, then every sublist of $L$ is also an $m$-list. One important consequence of this fact is that if we can show that there does not exist an $m$-list of length $k$, then we can conclude that there is no $m$-list that is longer than $k$. Thus, in general, if we want to prove that $k$ is the maximum length of an $m$-list, it suffices to do the following:

• Produce an example of an $m$-list of length $k$.

• Show that there does not exist an $m$-list of length $k+1$.

1. The list $[9,10]$ has $D(9)=9$ and $D(10)=1$, both of which are odd. Therefore, $[9,10]$ is a $2$-list of length $2$. We will now show that a list of three consecutive positive integers cannot be a $2$-list.

   Suppose $a$ is a positive integer with the property that $D(a)$ and $D(a+1)$ are both odd. Since $D(a)$ is odd, $D(a)+1$ is even. We are assuming that $D(a+1)$ is odd, and since $D(a)+1$ is even, we conclude that $D(a+1)\ne D(a)+1$.

   By Fact 1, the units digit of $a$ must be $9$ (otherwise $D(a+1)=D(a)+1$), so the units digit of $a+1$ is $0$. Again by Fact 1, $D(a+2)=D(a+1)+1$, and since $D(a+1)$ is odd, $D(a+1)+1=D(a+2)$ is even.

   Now consider the list $[a,a+1,a+2]$. If $D(a)$ and $D(a+1)$ are both odd, we have shown that $D(a+2)$ is even. This means it is impossible for $D(a)$, $D(a+1)$, and $D(a+2)$ to all be odd, so we conclude that a $2$-list of length $3$ cannot exist.

2. The arguments presented in this part and in part (d) rely on examining the location of multiples of $10$ in lists of consecutive integers. For this part, because of Fact 2, seven consecutive integers will have seven consecutive digit sums unless a multiple of $10$ causes a carry. To build a $7$-list of length more than six, there needs to be a multiple of $10$ somewhere in the middle to avoid ever having seven consecutive digit sums. You might be able to guess from this that the maximum length should be around $12$.

   Suppose $L=[a,a+1,a+2,\dots ,a+12]$ is an arbitrary list of $13$ consecutive non-negative integers. We will show that $L$ cannot be a $7$-list and this will show that a $7$-list cannot have length $13$.

   Since $L$ contains $13$ consecutive integers, it must contain at least one multiple of $10$. Thus, there must be some $k$ with $0\le k\le 12$ such that $a+k$ is a multiple of $10$.

   Case 1: $0\le k\le 6$.

   Since $k\le 6$, $a+k+6\le a+12$. The list $L$ contains the integers $a$ through $a+12$, so we conclude that the seven integers $a+k,a+k+1,\dots ,a+k+6$ are all in $L$. Moreover, the smallest multiple of $10$ after $a+k$ is $a+k+10$, so none of $a+k+1,a+k+2,\dots ,a+k+6$ is a multiple of $10$ since they are all strictly between two consecutive multiples of $10$.

   By Fact 2, the integers $D(a+k),D(a+k+1),\dots ,D(a+k+6)$ are consecutive. Any list of seven consecutive integers must contain a multiple of $7$, so we conclude that $L$ is not a $7$-list.

   Case 2: $7\le k\le 12$.

   Since $7\le k$, $a+7\le a+k$ which can be rearranged to get $a\le a+k-7$. By similar reasoning to the beginning of Case 1, the seven integers $a+k-7,a+k-6,\dots ,a+k-1$ are all in $L$. As well, they are strictly between $a+k-10$ and $a+k$, which are consecutive multiples of $10$. Therefore, none of $a+k-7,a+k-6,\dots ,a+k-1$ is a multiple of $10$.

   By Fact 2, $D(a+k-7),D(a+k-6),\dots ,D(a+k-1)$ are consecutive, so one of them must be a multiple of $7$. Therefore, $L$ is not a $7$-list.

   Cases 1 and 2 address all possibilities for the location of a multiple of $10$ in $L$. In both cases, $L$ is not a $7$-list. We conclude that a list of $13$ consecutive non-negative integers cannot be a $7$-list.

   To help find a $7$-list of length $12$, we can modify the reasoning above slightly. To that end, suppose $M=[a,a+1,a+2,\dots ,a+11]$ is a $7$-list. In the previous paragraphs, we essentially used the fact that if seven consecutive non-negative integers do not include a multiple of $10$, then one of their digit sums must be a multiple of $7$. Therefore, for $M$ to be a $7$-list, every sublist of seven-consecutive integers must contain a multiple of $10$. We leave it to the reader to verify that this forces $a+6$ to be a multiple of $10$.

   Since $a+6$ is a multiple of $10$, the closest multiples of $10$ to $a+6$ are $a-4$ and $a+16$. Therefore, the list $a,a+1,\dots ,a+5$ does not contain a multiple of $10$, and the only multiple of $10$ in the list $a+6,a+7,\dots ,a+11$ is $a+6$. By Fact 2, $$D(a),D(a+1),D(a+2),D(a+3),D(a+4),D(a+5)$$ and $$D(a+6),D(a+7),D(a+8),D(a+9),D(a+10),D(a+11)$$ are lists of six consecutive integers. We are assuming $M$ is a $7$-list, so no integer in either of these lists is a multiple of $7$. By Fact 3, the remainder after dividing $D(a+5)$ by $7$ is $7-1=6$. Also by Fact 3, the remainder after dividing $D(a+6)$ by $7$ is $1$.

   To summarize, if $M=[a,a+1,\dots ,a+11]$ is a $7$-list, then the following must be true.

   • $a+6$ is a multiple of $10$.

   • The remainder after dividing $D(a+5)$ by $7$ is $6$.

   • The remainder after dividing $D(a+6)$ by $7$ is $1$.

   The first condition implies that $a+5$ has a units digit of $9$, so suppose that $n+5$ has $t$ trailing $9$s. By Fact 4, $D(n+6)-D(n+5)=1-9t$. The second two conditions imply that there are integers $m$ and $n$ such that $D(a+5)=7n+6$ and $D(a+6)=7m+1$. Substituting into $D(a+6)-D(a+5)=1-9t$, we obtain $(7n+1)-(7m+6)=1-9t$ which can be rearranged to get $2t-6=7(m-n-t)$. We know that $t$ is a positive integer, and this shows that $2t-6$ must be a multiple of $7$. The smallest positive integer $t$ with the property that $2t-6$ is a multiple of $7$ is $t=3$ since $2(3)-6=0$, which is a multiple of $7$.

   We are looking for an integer $a$ such that $a+5$ ends in three $9$s and has the property that $D(n+5)$ is six more than a multiple of $7$. Thus, $a+5$ will have the form $x999$ where $x$ is some string of digits. In fact, $D(999)=9+9+9=27$ has a remainder of $6$ when divided by $7$, so we set $a+5=999$ or $a=994$. Indeed, if we set $$M=[994,995,996,997,998,999,1000,1001,1002,1003,1004,1005]$$ the digit sums of the integers in $M$ are $22,23,24,25,26,27,1,2,3,4,5,6$, none of which is a multiple of $7$. Therefore, $M$ is a $7$-list of length $12$.

   This is actually the earliest $7$-list of length $12$. Others can be found by prepending digits to 994 in such a way that the number of trailing $9$s of $a+5$ does not change, and the remainder after dividing the digit sum by $7$ does not change. This can be done by prepending any digits that have a sum that is a multiple of $7$, provided the rightmost new digit is not a $9$.

   For example, we could take $a$ to be $7994$, $16994$, $25994$, $662994$, and so on.

3. Following the reasoning from (b), one might think that we can find a $9$-list of length $8+8=16$. Specifically, we might expect that we can find a list of the form $[a,a+1,\dots ,a+15]$ where $a+8$ is a multiple of $10$ so that there are never nine consecutive integers without a multiple of $10$. In fact, the maximum length of a $9$-list is eight, so the approach in part (b) cannot be applied here. You might like to try to follow the reasoning from part (b) through to see exactly what goes wrong. The proof given here uses the well-known fact that a positive integer $n$ is a multiple of $9$ if and only if $D(n)$ is a multiple of $9$.

   A list of nine consecutive integers must contain a multiple of $9$, so it must contain an integer whose digit sum is a multiple of $9$. Therefore, a list of $9$ consecutive integers cannot be a $9$-list.

   Any list of eight consecutive integers, none of which is a multiple of $9$, must be a $9$-list since none of the digit sums are multiples of $9$. An example of a $9$-list of length $8$ is $[1,2,3,4,5,6,7,8]$.

4. It might come as a surprise, but the maximum length of an $11$-list is $38$.

   To get an idea of how one might guess this, we will first determine the maximum length of an $11$-list that starts with a multiple of $10$.

   Suppose $L=[a,a+1,a+2,\dots ,a+19]$ is an $11$-list of length $20$ with the property that $a$ is a multiple of $10$. By Fact 2, $D(a),D(a+1),\dots ,D(a+9)$ and $D(a+10),D(a+11),\dots ,D(a+19)$ are lists of ten consecutive integers. Since we are assuming that $L$ is an $11$-list, no integer in either of these lists is a multiple of $11$. Therefore, by Fact 3, the remainder after $D(a+9)$ is divided by $11$ is $10$ and the remainder after $D(a+10)$ is divided by $11$ is $1$. This implies the existence of integers $m$ and $n$ such that $D(a+9)=11m+10$ and $D(a+10)=11n+1$.

   Since $a$ is a multiple of $10$, the units digit of $a+9$ is $9$. Suppose $a+9$ has $t$ trailing $9$s. By Fact 4, $D(a+10)-D(a+9)=1-9t$. Substituting $D(a+9)=11m+10$ and $D(a+10)=11n+1$ into this equation, we get $$(11n+1)-(11m+10)=1-9t$$ which can be rearranged to get $9t=11(m-n)+10$. This means $t$ is a positive integer with the property that $9t$ is ten more than a multiple of $11$. It can be checked that $t=6$ is the smallest positive integer with this property.

   We have shown the following: if $[a,a+1,a+2,\dots ,a+19]$ is an $11$-list of length $20$ with the property that $a$ is a multiple of $10$, then $a+9$ has at least six trailing $9$s. We can use this fact to prove the following:

   1. An $11$-list that starts with a multiple of $10$ cannot have length $30$.

   2. An $11$-list cannot have length $39$.

   To prove (i), assume that $L=[a,a+1,a+2,\dots ,a+29]$ is an $11$-list of length $30$ and that $a$ is a multiple of $10$. We will show that this implies something that is plainly false, which will allow us to conclude that such an $11$-list cannot exist.

   The fact that $L$ is an $11$-list implies that the lists $M=[a,a+1,\dots ,a+19]$ and $N=[a+10,a+11,\dots ,a+29]$ are both $11$-lists. Moreover, $a$ is a multiple of $10$, so $a+10$ is a multiple of $10$. Thus, $M$ and $N$ are both $11$-lists of length $20$ that start with a multiple of $10$. By what was established earlier, both $a+9$ and $a+10+9=a+19$ have at least six trailing $9$s.

   The difference between two integers with at least six trailing $9$s must have at least six trailing $0$s. However, $(a+19)-(a+9)=10$ has only one trailing $0$. We have shown that if an $11$-list starts with a multiple of $10$ and has length $30$, then $10$ has at least six trailing $0$s. Since $10$ has only one trailing $0$, we conclude that it must be impossible for an $11$-list to have length $30$ and start with a multiple of $10$. Note: The technique just used is known as a proof by contradiction.

   To prove (ii), we can apply (i). Suppose $L=[a,a+1,a+2,\dots ,a+38]$ is a list of $39$ consecutive positive integers. Among the first ten integers in $L$, there must be a multiple of $10$. Suppose $k$ is an integer with $0\le k\le 9$ such that $a+k$ is a multiple of $10$. Observe that $a+k+29\le a+9+29=a+38$, which means the list $M=[a+k,a+k+1,\dots ,a+k+29]$ is completely contained in $L$. The list $M$ has length $30$ and starts with a multiple of $10$, so it cannot be an $11$-list by (i). Since $L$ contains a sub-list that is not an $11$-list, it cannot be an $11$-list. Therefore, an $11$-list cannot have length $39$.

   We can now use what we have done to find an $11$-list of length $38$. Suppose that $L=[a,a+1,a+2,\dots ,a+37]$ is an $11$-list. There must be an integer $k$ with $0\le k\le 9$ such that $a+k$ is a multiple of $10$. If $0\le k\le 8$, then $a+k+29\le a+37$, so $[a+k,a+k+1,\dots ,a+k+29]$ is entirely contained in $L$. This would imply the existence of an $11$-list of length $30$ that starts with a multiple of $10$, which is impossible by (i). Since $0\le k\le 8$ is impossible, we conclude that $k=9$.

   We assumed that $L=[a,a+1,a+2,\dots ,a+37]$ was an $11$-list and deduced that $a+9$ is a multiple of $10$. The list $[a+9,a+10,\dots ,a+28]$ is completely contained in $L$, has length $20$, and starts with a multiple of $10$. Therefore, from the argument at the beginning of the solution to this part, $a+9+9=a+18$ has at least six trailing $9$s. As well, Since $a+9$ is a multiple of $10$, we can apply Fact 2 to $a+9,a+10,\dots ,a+18$ to get that $D(a+9),D(a+10),\dots ,D(a+18)$ is a list of $10$ consecutive integers. Since $L$ is an $11$-list, none of them is a multiple of $11$. By Fact 3, the remainder after $D(a+18)$ is divided by $11$ is $10$.

   Therefore, we will look for an integer $a$ with the property that $a+18$ has $6$ trailing $9$s and $D(a+18)$ is $10$ more than a multiple of $11$. The integer $999999$ has $D(999999)=54$ which is $10$ more than a multiple of $11$, so we guess that $a+18=999999$, or $a=999981$. It can be checked that the list $[999981,999982,\dots ,1000018]$ is an $11$-list of length $38$. It also follows from our reasoning that this is the first such $11$-list.