D/2 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 .)
Solution: 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:

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 :
\begin{tabular}{cccccccccc} 
& 3 & 2 & 8 & 3 & 4 & 6 & 7 & 8 & 5 \\
$\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ \\
0 & 3 & 5 & 13 & 16 & 20 & 26 & 33 & 41 & 46 \\
$\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ & $\downarrow$ \\
0 & 3 & 5 & 4 & 7 & 2 & 8 & 6 & 5 & 1
\end{tabular}

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 :
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.