Serbian Mathematical Olympiad

Solution:

Since $2009 = 223 \cdot 9 + 2$, the desired number has at least $224$ digits. We shall consider $224$-digit numbers $x = \overline{c_{223} c_{222} \ldots c_{1} c_{0}}$. It is clear that $c_{223} \geq 2$. Moreover, if $c_{223} = 2$ then $c_{222} = \cdots = c_{0} = 9$ and $x = 3 \cdot 10^{223} - 1 \equiv 3 \cdot 10 - 1$, and this is not divisible by $2009 = 7^{2} \cdot 41$ since $x \equiv 1 \pmod{7}$.

Now let $c_{223} = 3$. Then the number $x$ has the form $399\ldots 9899\ldots 9 = 4 \cdot 10^{223} - 10^{i} - 1$ for some $i$. Since $10^{5} \equiv 1 \pmod{41}$, we have $10^{i} \equiv 1, 10, 18, 16$ or $37 \pmod{41}$ for $i = 0, 1, 2, 3, 4 \pmod{5}$ respectively, and from this $x \equiv 4 \cdot 10^{3} - 10^{i} - 1 \equiv 22 - 10^{i} \pmod{41}$ is never divisible by $41$.

Let $c_{223} = 4$. Among the digits $c_{222}, \ldots, c_{0}$ there are either two eights or one seven, while all the others are nines; in every case, $x = 5 \cdot 10^{223} - 10^{i} 10^{j} - 1 \equiv 38 - (10^{i} + 10^{j}) \pmod{41}$, where $i$ and $j$ are not necessarily distinct. By the previous, $10^{i} + 10^{j} \equiv 38 \pmod{41}$ if and only if $(i, j) \equiv (0, 4)$ or $(4, 0) \pmod{5}$. Among other things, $i \neq j$ and $i, j \leq 220$.

Let us try setting $j = 220$ and $i \equiv 4 \pmod{5}$. We need to choose $i$, if it exists, so that $7^{2} \mid x = 5 \cdot 10^{223} - 10^{220} - 10^{i} - 1 \equiv 5 \cdot 10^{13} - 10^{10} - 10^{i} - 1 \equiv 31 - 10^{i} \pmod{49}$. We easily find that $10^{i} \equiv 31 \pmod{49}$ if and only if $i \equiv 7 \pmod{42}$, which together with $i \equiv 4 \pmod{5}$ gives as the only possibility $i = 49$. Therefore, the desired number is

$$4998\underbrace{9 \ldots 99}_{170}8\underbrace{99 \ldots 9}_{49}.$$