XXXI Brazilian Math Olympiad

First notice that $10$ is a multiple of $5=2\cdot 2+1$, so we are done if $q$ and $10$ are not coprime. If $q$ and $10$ are coprime, since $q$ is prime, by Fermat's theorem $q\mid 10^{q-1}-1\iff q\mid 10^{2p}-1\iff q\mid 10^p-1$ or $q\mid 10^p+1$. If $q\mid 10^p+1$, we are done: the sum of the digits of $10^p+1$ is $2$. From now on, suppose that $q\mid 10^p-1$.

Consider the minimum positive integer $d$ such that $10^d\equiv 1(\mathrm{mod}q)$, that is, $d={\text{ord}}_{q}10$. Then $d\mid p$, that is, the possible values of $d$ are $1$ and $p$. If $d=1$, $q\mid 10^1-1\iff q=3$, which is not acceptable. So $d=p$, which means that $1,10,10^2,\dots ,10^{p-1}$ are all distinct mod $q$.

Now let $A=\{0\}\cup \{10^k\text{ mod }q:0\le k<p\}$ and $B=\{q-1\}\cup \{-1-10^k\text{ mod }q:0\le k<p\}$. Since $10^k\not\equiv 0(\mathrm{mod}q)$, $|A|=|B|=p+1$. This and the obvious fact that $|A\cup B|\le q=2p+1$ implies $A\cap B\ne \varnothing$.

So either there are integers $r,s$ such that $10^r\equiv -1-10^s(\mathrm{mod}q)$, in which case $10^r+10^s+1$, whose digit sum is $3$, is a multiple of $q$, or $10^r\equiv -1(\mathrm{mod}q)$, in which $10^r+1$, whose digit sum is $2$, is a multiple of $q$, or $0\equiv -1-10^s(\mathrm{mod}q)$, which is analogous to the previous case. So, in all cases, we are done.