Olimpíadas(Rufino) Indução Finita 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 ]

Autor do Tópico
Auto Excluído (ID:17906)
6 - Doutor
Última visita: 31-12-69
Fev 2018 09 23:30

(Rufino) Indução Finita

Mensagem não lida por Auto Excluído (ID:17906) »

Prove por indução que todos os números da forma [tex3]1007, 10017, 100117, ...[/tex3] são divisíveis por [tex3]53[/tex3] .




Avatar do usuário
PedroCosta
2 - Nerd
Mensagens: 179
Registrado em: Ter 02 Jan, 2018 19:21
Última visita: 23-06-21
Fev 2018 10 01:18

Re: (Rufino) Indução Finita

Mensagem não lida por PedroCosta »

Creio que seja isso:
Sabemos que [tex3]53|1007[/tex3] é uma proposição válida.
Supomos que [tex3]53|100\underbrace{1...1}_k7[/tex3] é uma proposição verdadeira.
Deve ser verdadeira também para [tex3]53|100\underbrace{1...1}_{k+1}7[/tex3] .
[tex3]53m-53n = 100\underbrace{1...1}_{k+1}7-100\underbrace{1...1}_{k}7\\
53m-53n = 901\cdot 10^{k+1}\\
53(m-n) = 901\cdot 10^{k+1}\\
t = m-n\\
53t = 901\cdot 10^{k+1} \Longleftrightarrow 53|901\cdot 10^{k+1}\\
53|901 \Longrightarrow 53|901\cdot 10^{k+1}[/tex3]
Como o processo é reversível:
[tex3]53|100\underbrace{1...1}_{k+1}7[/tex3]

Última edição: PedroCosta (Sáb 10 Fev, 2018 11:00). Total de 2 vezes.


"Se vai tentar, vá até o fim.
Caso contrário, nem comece.
Se vai tentar, vá até o fim.
Pode perder namoradas, esposas, parentes, empregos e talvez até a cabeça.
Vá até o fim."
Charles Bukowski

Avatar do usuário
rodBR
4 - Sabe Tudo
Mensagens: 592
Registrado em: Sáb 28 Jan, 2017 22:37
Última visita: 04-03-24
Fev 2018 10 01:36

Re: (Rufino) Indução Finita

Mensagem não lida por rodBR »

Olá GuiBernardo, boa noite.

Preliminares:
Inicialmente, vamos escrever os termos dessa sequência:
[tex3]\begin{cases}
a_0=10^3+10^0+6\\
a_1=10^4+10^1+10^0+6\\
a_2=10^5+10^2+10^1+10^0+6\\
.\\
.\\
.
\end{cases}[/tex3]

Então o termo geral [tex3]a_n[/tex3] , é dado por:
[tex3]a_n=10^{n+3}+(10^{n}+10^{n-1}+...+10^1+10^0)+6[/tex3]
[tex3]\boxed{\boxed{a_n=10^{n+3}+\sum_{i=0}^{n}10^i+6}}[/tex3]

Demonstração:
I) Se [tex3]n=0[/tex3] , então:
[tex3]a_n=10^{n+3}+\sum_{i=0}^{n}10^i+6[/tex3]
[tex3]a_0=10^{0+3}+\sum_{i=0}^{0}10^i+6=1000+1+6=1007 \ \therefore 53 \ |\ 1007=19\cdot53[/tex3] . (OK!)

II) Vamos assumir que vale para [tex3]n=n_0[/tex3] , isto é:
[tex3]53 \ | \ a_{n_0}=10^{n_0+3}+\sum_{i=0}^{n_0}10^i+6 \implies a_{n_0}=53k \ \ \ \ (*)[/tex3] .

III) Para [tex3]n_{0+1}[/tex3] , temos:
[tex3]a_{n_0+1}=10^{n_0+4}+\sum_{i=0}^{n_0+1}10^i+6[/tex3]
[tex3]a_{n_0+1}=10^{n_0+4}+\sum_{i=0}^{n_0}10^i+10^{n_0+1}+6[/tex3] . Some e subtraia [tex3]10^{n_0+3}[/tex3] :
[tex3]a_{n_0+1}=10^{n_0+3}+10^{n_0+4}+\sum_{i=0}^{n_0}10^i+10^{n_0+1}+6-10^{n_0+3}[/tex3]
[tex3]a_{n_0+1}=(10^{n_0+3}+\sum_{i=0}^{n_0}10^i+6)+(-10^{n_0+3}+10^{n_0+4}+10^{n_0+1})[/tex3] . Evidencie [tex3]10^{n_0+1}[/tex3] no segundo parenteses:
[tex3]a_{n_0+1}=(10^{n_0+3}+\sum_{i=0}^{n_0}10^i+6)+10^{n_0+1}\cdot(-10^{2}+10^{3}+1)[/tex3]
[tex3]a_{n_0+1}=(10^{n_0+3}+\sum_{i=0}^{n_0}10^i+6)+10^{n_0+1}\cdot(-100+1000+1)[/tex3]
[tex3]a_{n_0+1}=(10^{n_0+3}+\sum_{i=0}^{n_0}10^i+6)+10^{n_0+1}\cdot(901)[/tex3]
[tex3]a_{n_0+1}=(10^{n_0+3}+\sum_{i=0}^{n_0}10^i+6)+10^{n_0+1}\cdot(17\cdot53)[/tex3] . De [tex3](*)[/tex3] , temos:
[tex3]a_{n_0+1}=53k+10^{n_0+1}\cdot17\cdot53[/tex3] . Coloque [tex3]53[/tex3] , em evidência:
[tex3]a_{n_0+1}=53k+10^{n_0+1}\cdot17) \implies 53 \ | \ a_{n_0+1}[/tex3] .




obs: O colega já havia enviado a solução enquanto estava digitando, mas vou deixar... :D

Última edição: rodBR (Sáb 10 Fev, 2018 15:54). Total de 1 vez.


"Uma vida sem questionamentos não merece ser vivida".

Movido de IME / ITA para Olimpíadas em Qui 15 Fev, 2018 12:28 por ALDRIN

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

Voltar para “Olimpíadas”