
NT11 Determine the greatest number with $n$ digits in the decimal representation which is divisible by 429 and has the sum of all digits less than or equal to 11 .


## Solution

Let $A=\overline{a_{n} a_{n-1} \ldots a_{1}}$ and notice that $429=3 \cdot 11 \cdot 13$.

Since the sum of the digits $\sum a_{i} \leq 11$ and $\sum a_{i}$ is divisible by 3 , we get $\sum a_{i}=3,6$ or 9. As 11 divides $A$, we have

$$
11 \mid a_{n}-a_{n-1}+a_{n-2}-a_{n-3}+\ldots
$$

in other words $11 \mid \sum_{i \text { odd }} a_{i}-\sum_{i \text { even }} a_{i}$. But

$$
-9 \leq-\sum a_{i} \leq \sum_{i \text { odd }} a_{i}-\sum_{i \text { even }} a_{i} \leq \sum a_{i} \leq 9
$$

so $\sum_{i \text { odd }} a_{i}-\sum_{i \text { even }} a_{i}=0$. It follows that $\sum a_{i}$ is even, so $\sum a_{i}=6$ and $\sum_{i \text { odd }} a_{i}=\sum_{i \text { even }} a_{i}=3$.

The number 13 is a divisor of 1001 , hence

$$
13 \mid \overline{a_{3} a_{2} a_{1}}-\overline{a_{6} a_{5} a_{4}}+\overline{a_{9} a_{8} a_{7}}-\overline{a_{12} a_{11} a_{10}}+\ldots
$$

For each $k=1,2,3,4,5,6$, let $s_{k}$ be the sum of the digits $a_{k+6 m}, m \geq 0$; that is

$$
s_{1}=a_{1}+a_{7}+a_{13}+\ldots \text { and so on. }
$$

With this notation, (1) rewrites as

$$
13 \mid 100\left(s_{3}-s_{6}\right)+10\left(s_{2}-s_{5}\right)+\left(s_{1}-s_{4}\right), \text { or } 13 \mid 4\left(s_{6}-s_{3}\right)+3\left(s_{5}-s_{2}\right)+\left(s_{1}-s_{4}\right)
$$

Let $S_{3}=s_{3}-s_{6}, S_{2}=s_{2}-s_{5}$, and $S_{1}=s_{1}-s_{4}$. Recall that $\sum_{i \text { odd }} a_{i}=\sum_{i \text { even }} a_{i}$, which implies $S_{2}=S_{1}+S_{3}$. Then

$$
13\left|4 S_{3}+3 S_{2}-S_{1}=7 S_{3}+2 S_{1} \Rightarrow 13\right| 49 S_{3}+14 S_{1} \Rightarrow 13 \mid S_{1}-3 S_{3}
$$

Observe that $\left|S_{1}\right| \leq s_{1}=\sum_{i \text { odd }} a_{i}=3$ and likewise $\left|S_{2}\right|,\left|S_{3}\right| \leq 3$. Then $-13<S_{1}-3 S_{3}<13$ and consequently $S_{1}=3 S_{3}$. Thus $S_{2}=4 S_{3}$ and $\left|S_{2}\right| \leq 3$ yields $S_{2}=0$ and then $S_{1}=S_{3}=0$. We have $s_{1}=s_{4}, s_{2}=s_{5}, s_{3}=s_{6}$ and $s_{1}+s_{2}+s_{3}=3$, so the greatest number $A$ is $30030000 \ldots$.
