Problem of the Month
Hint for Problem 1: October 2023

For an integer $a$, think about how $D(a)$ and $D(a+1)$ compare to each other. The relationship is most interesting when $a+1$ is a multiple of $10$.

Our solution will make use of some basic properties of remainders. For positive integers $a$ and $b$, the remainder when dividing $a$ by $b$ can be found by first determining $qb$, the greatest multiple of $b$ with $qb\le a$, then computing the remainder as $r=a-qb$. The integer $q$ can be found by computing ${\displaystyle \frac{a}{b}}$ and rounding down. For example, the remainder when dividing $38$ by $5$ is $3$ because $35$ is the greatest multiple of $5$ that does not exceed $38$ (in this case, $q=7$), and so the remainder is $38-35=3$. We assume this idea is familiar, but here are a couple of things to think about and keep in mind.

• For integers $a$ and $b$ with $b>0$, the remainder, $r$, when dividing $a$ by $b$ satisfies $0\le r<b$.

• For a fixed positive integer $b$, the remainders when dividing the positive integers $1,2,3,4,5,\dots$ cycle through the integers $1,2,3,\dots ,b-2,b-1,0$ repeatedly in that order. Importantly, if we think of $0$ as coming "after" $b-1$, the remainders for consecutive integers are consecutive.

• The remainder when dividing $a$ by $b$ is $0$ exactly when $a$ is a multiple of $b$.

If you have seen modular arithmetic before, it could be useful in writing a solution. Our solution will not use modular arithmetic, but we suggest reading about it anyway since it is quite useful.

Below are some specific hints for the given questions.

1. Show that if $D(a)$ and $D(a+1)$ are both odd, then $a+1$ is a multiple of $10$.

2. First, try to find the maximum length of a $7$-list that does not contain a multiple of $10$. For an integer $a$, how do the remainders when $D(a)$ and $D(a+1)$ are divided by $7$ relate to each other?

3. By a rather famous divisibility rule, a positive integer is a multiple of $9$ if and only if the sum of its digits is a multiple of $9$.

4. First show that an $11$-list that starts with a multiple of $10$ has length at most $29$. Think about the remainders when $D(a)$ and $D(a+1)$ are divided by $11$.