Given a positive integer $N$ (written in base 10), define its integer substrings to be integers that are equal to strings of one or more consecutive digits from $N$, including $N$ itself. For example, the integer substrings of 3208 are $3,2,0,8,32,20,320,208$, and 3208. (The substring 08 is omitted from this list because it is the same integer as the substring 8 , which is already listed.)

What is the greatest integer $N$ such that no integer substring of $N$ is a multiple of 9? (Note: 0 is a multiple of 9.)
The answer is $88,888,888$.

In our solution, we'll make use of the well-known fact that an integer is divisible by 9 if and only if the sum of its digits (in base 10) is divisible by 9. It was permissible to use this fact without proof on the contest, but for the sake of completeness, a proof can be found in the appendix following this solution.

No integer substring of $88,888,888$ is divisible by 9 , since 9 does not divide $8 k$ for any $k=1, \ldots, 8$.

We now show that every $N>88,888,888$ has an integer substring divisible by 9 .

Suppose $N>88,888,888$. If $N$ has 8 digits, then one of those digits must be 9 , which constitutes an integer substring by itself, so we are done. Thus, we assume from now on that $N$ has 9 or more digits.

We claim that for any such $N$, there is some integer substring divisible by 9 . In fact, we will describe an algorithm to find such a substring, using $N=328,346,785$ as an illustrative example. For $0 \leq k \leq$ 9 , let $s_{k}$ be the sum of the first $k$ digits of $N$, where we define $s_{0}$ to be 0 . We can think of $s_{k}$ as a "running total" of the digits; here is our example number with $s_{0}, \ldots, s_{9}$ written below it:

![](https://cdn.mathpix.com/cropped/2024_04_17_6cb05c45fe7c141f3316g-3.jpg?height=147&width=558&top_left_y=1428&top_left_x=729)

Next we consider the remainders left by $s_{0}, \ldots, s_{9}$ when they are divided by 9 . We have ten remainders with only nine possible values. By the pigeonhole principle, some two remainders must be equal. For instance, in our example, two of the remainders are equal to 5 :

![](https://cdn.mathpix.com/cropped/2024_04_17_6cb05c45fe7c141f3316g-3.jpg?height=241&width=583&top_left_y=1766&top_left_x=714)

Suppose it is $s_{j}$ and $s_{k}$ that leave the same remainder (where $j<k$ ). Then $s_{k}-s_{j}$ is divisible by 9 . But $s_{k}-s_{j}$ is the sum of the digits of the integer substring consisting of the $(j+1)^{\text {th }}$ through $k^{\text {th }}$ digits of $N$. In the example above, for instance, this substring is 834678 :

![](https://cdn.mathpix.com/cropped/2024_04_17_6cb05c45fe7c141f3316g-3.jpg?height=136&width=496&top_left_y=2206&top_left_x=760)

and we have $8+3+4+6+7+8=41-5=36$, a multiple of 9 .

Since we have an integer substring whose digits add up to a multiple of 9 , that substring is itself a multiple of 9 , and we are finished.

Appendix. Here is the proof of the "well-known fact" mentioned at the beginning. To keep the notation simple, we state the proof for 4-digit integers; it should be clear how to generalize to integers with any number of digits.

Let $n=\underline{a b c d}$, where the underline means we are writing the digits of $n$. By the nature of base 10 representation, we have

$$
\begin{aligned}
n & =1000 a+100 b+10 c+d \\
& =(999+1) a+(99+1) b+(9+1) c+d \\
& =(999 a+99 b+9 c)+(a+b+c+d) .
\end{aligned}
$$

The first bracketed quantity is a multiple of 9 . Thus, $n$ and $a+b+c+d$ differ by a multiple of 9 . In particular, if $n$ is a multiple of 9 , then so is $a+b+c+d$ (the sum of its digits), and vice versa. This completes our proof.