OBM 2018 - Nível 3 - P5

Problema

Considere a sequência em que $a_1=1$ e $a_n$ é obtido justapondo o final da representação decimal de $a_{n-1}$ a representação decimal de $n$. Ou seja: $a_1=1,\:a_2=12,\:a_3=123,...,a_9=123456789,\:a_{10}=12345678910$ e assim sucessivamente. Prove que infinitos termos dessa sequência são múltiplos de $7$.

Solução de Jonatan de Lima:

Para $k$ suficientemente grande, vamos olhar para os índices da forma $10^k+i$. Assim, nesse caso vale que $a_{10^k+i+1}=a_{10^k+i}\cdot 10^{k+1}+10^k+1+i$, com $i<9\cdot10^k$. Seja então $b_i=a_{10^k+i}$ para facilitar notação, com $i$ no intervalo já informado,e $\alpha\equiv10^{k+1}\:(mod\:7)$. Vamos telescopar nossas equações:

$b_1=\alpha\cdot b_0+10^k+1$

$b_2=\alpha\cdot b_1+10^k+2$

$\vdots$

$b_6=\alpha\cdot b_5+10^k+6$

O que é melhor reescrito como:

$\alpha^5\cdot b_1=\alpha^6\cdot b_0+\alpha^5(10^k+1)$

$\alpha^4\cdot b_2=\alpha^5\cdot b_1+\alpha^4(10^k+2)$

$\vdots$

$\alpha\cdot b_5=\alpha^2\cdot b_4+\alpha(10^k+5)$

$b_6=\alpha\cdot b_5+10^k+6$

Donde concluímos que: $b_6=\alpha^6\cdot b_0+10^k(1+\alpha+\cdots+\alpha^5) +\alpha^5+2\alpha^4+3\alpha^3+4\alpha^2+5\alpha+6$ e tomando $\alpha\neq 1$ temos que $1+\alpha+\cdots+\alpha^5=\dfrac{\alpha^6-1}{\alpha-1}$, mas pelo Teorema de Fermat, como $7\nmid\alpha$, vale que $\alpha^6\equiv 1\:(mod\:7)\Rightarrow 1+\alpha+\cdots+\alpha^5\equiv0\:(mod\:7)$. Além disso, $\alpha^5+2\alpha^4+3\alpha^3+4\alpha^2+5\alpha+6\equiv \alpha^5-5\alpha^4+10\alpha^3-10\alpha^2+5\alpha-1\equiv (\alpha-1)^5\:(mod\:7)$, e portanto $b_6\equiv b_0+(\alpha-1)^5\:(mod\:7)$. Com isso, podemos concluir que $b_{6l}\equiv b_0+l\cdot(\alpha-1)^5\:(mod\:7)$, e como $7$ é primo, $7|(\alpha-1)^5\iff \alpha\equiv 1\:(mod\:7)$, caso que já foi excluido, e logo basta tomar $l\in[0,6]$ tal que $l\equiv -(\alpha-1)\cdot b_0\:(mod\:7)$ para obtermos $7|b_{6l}\Rightarrow 7|a_{10^k+6l}$. Como existem infinitos $k$ tal que $\alpha\equiv10^k$ não é congruente à $1$ módulo $7$, já que basta que ele não seja divisível por $6$, que é a ordem de $10$ módulo $6$, segue que infinitos termos da sequência são múltiplos de $7$.