, 2008

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+6m}, 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(s_3 - s_6) + 10(s_2 - s_5) + (s_1 - s_4), \text{ or } 13 \mid 4(s_6 - s_3) + 3(s_5 - s_2) + (s_1 - s_4)$$
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 \mid 4S_3 + 3S_2 - S_1 = 7S_3 + 2S_1 \Rightarrow 13 \mid 49S_3 + 14S_1 \Rightarrow 13 \mid S_1 - 3S_3$$
Observe that $|S_1| \leq s_1 = \sum_{i \text{ odd}} a_i = 3$ and likewise $|S_2|, |S_3| \leq 3$. Then $-13 < S_1 - 3S_3 < 13$ and consequently $S_1 = 3S_3$. Thus $S_2 = 4S_3$ and $|S_2| \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$.