Olimpíadas ⇒ Qtd de Inteiros Positivos Tópico resolvido

[quevedo]

Ghandi (Problemas selecionados)

O número de inteiros positivos cuja representação decimal apresenta somente os algarismos 2 e 5 possui 2005 algarismos e é divisível por [tex3]2^{2005}[/tex3] é igual a:

a) 0
b) 1
c) 2
d) 3
e) mais de 3

Resposta

---

B

Sei que um número é divisível por [tex3]2^{n}[/tex3] quando os n últimos algarismos são divisíveis por ele. Testando sei que 4|52; 8|552; 16|5552; 32|55552; 64|255552. Alguém pode me ajudar?

[Ittalo25MOD]

Achei uma solução parecida que dá para ser usada: Divisibility by Powers of 2. Não consegui digerir a parte em negrito, alguém consegue explicar?

A ideia é começar testando mesmo, você pegou: [tex3]x_1=52, x_2=552,x_3=5552,etc...[/tex3]

Generalizando, dá para tomar o número [tex3]x_{n}[/tex3] tendo n dígitos (2's e 5's) e sendo divisível por [tex3]2^{n}[/tex3]

Se [tex3]x_{n}[/tex3] for divisível por [tex3]2^{n+1}[/tex3], simplesmente fazemos [tex3]x_{n+1} = 2\cdot 10^{n}+ x_{n} = 2^{n+1}\cdot 5^n+x_n[/tex3]. Ou seja, temos [tex3]x_{n+1} [/tex3] com n+1 dígitos (Já que somamos [tex3]2\cdot 10^{n}[/tex3]) e divisível por [tex3]2^{n+1}[/tex3].

Se [tex3]x_{n}[/tex3] não for divisível por [tex3]2^{n+1}[/tex3], o resultado da divisão vai ser algo decimal do tipo [tex3]\overline{abcd...}, 5 [/tex3].
Do mesmo jeito, temos que [tex3]5\cdot 10^{n}[/tex3] dividido por [tex3]2^{n+1}[/tex3] vai dar um resultado decimal [tex3]\overline{efgh...}, 5 [/tex3].
Ora, então fazemos: [tex3]x_{n+1} = 5\cdot 10^n+x_{n}[/tex3].
Esse número tem n+1 dígitos, já que somamos [tex3]5\cdot 10^{n}[/tex3].
Esse número é divisível por [tex3]2^{k+1}[/tex3], já que os dois resultados decimais 0,5 foram somados.

Então por indução, a sequência [tex3]\{x_1,x_2,x_3,...x_n\} [/tex3] é infinita. Ou seja, existe pelo menos um [tex3]x_{2005} [/tex3].

E ele é único, já que o [tex3]x_n [/tex3] sempre depende do [tex3]x_{n-1} [/tex3], como vimos na indução.

Sendo assim, a resposta é Letra B)

[Ittalo25MOD]

Encontrei uma explicação do Gugu neste vídeo: Teoria dos Números ( Ordem e raízes primitivas ) - Nível 3

Negócio é que se [tex3]2^{n+1} [/tex3] não divide [tex3]x_n [/tex3], então [tex3]\frac{x_n}{2^n}[/tex3] é ímpar.

Sendo assim, [tex3]2^{n+1}[/tex3] divide [tex3]2^n \cdot (\frac{x_n}{2^n}+5^{n+1}) = x_n + 5\cdot 10^n[/tex3]

Agora sim, muito boa questão