OlimpíadasQtd de Inteiros Positivos Tópico resolvido

Aqui devem ser postados problemas Olímpicos. Informe a olimpíada e o ano no título do tópico. Exemplo: (OBM - 2008).

Moderador: [ Moderadores TTB ]

Avatar do usuário
Autor do Tópico
quevedo
sênior
Mensagens: 43
Registrado em: Qua 20 Abr, 2016 17:52
Última visita: 03-05-23
Mar 2019 10 10:34

Qtd de Inteiros Positivos

Mensagem não lida por 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?

Última edição: caju (Dom 10 Mar, 2019 11:14). Total de 1 vez.
Razão: arrumar título.



Avatar do usuário
Ittalo25
5 - Mestre
Mensagens: 2349
Registrado em: Seg 18 Nov, 2013 22:11
Última visita: 27-03-24
Mar 2019 10 16:02

Re: Qtd de Inteiros Positivos

Mensagem não lida por Ittalo25 »

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)



Ninguém pode ser perfeito, mas todos podem ser melhores. [\Bob Esponja]

Avatar do usuário
Ittalo25
5 - Mestre
Mensagens: 2349
Registrado em: Seg 18 Nov, 2013 22:11
Última visita: 27-03-24
Mar 2019 11 21:52

Re: Qtd de Inteiros Positivos

Mensagem não lida por Ittalo25 »

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 :arrow:



Ninguém pode ser perfeito, mas todos podem ser melhores. [\Bob Esponja]

Responder
  • Tópicos Semelhantes
    Respostas
    Exibições
    Última msg

Voltar para “Olimpíadas”