Mostre que não existe uma função [tex3]f:\mathbb{N}\rightarrow \mathbb{N}[/tex3]
Nota: eu sei que há outra forma de fazer esta questão, mas eu gostaria de ver uma resolução utilizando o Princípio da Indução Finita, visto que esta questão, no meu livro, está na parte que aborda esta matéria.
tal que [tex3]f(f(n))=n+1987,\ \forall \ n\ \in \ \mathbb{N} [/tex3]
.Olimpíadas ⇒ (IMO - 1987) Princípio da Indução Finita Tópico resolvido
Moderador: [ Moderadores TTB ]
Jan 2018
24
00:55
(IMO - 1987) Princípio da Indução Finita
Última edição: GiovanaM (Qua 24 Jan, 2018 10:51). Total de 1 vez.
-
- Última visita: 31-12-69
Jan 2018
24
03:46
Re: (IMO - 1989) Princípio da Indução Finita
Assuma que exista tal função.
Aplique [tex3]n = f(m)[/tex3] então [tex3]f(f(f(m))) = f(m) + 1987[/tex3]
e é claro que [tex3]f(f(f(m))) = f(m+1987)[/tex3]
então a parte da indução é a seguinte:
deixe [tex3]t[/tex3] ser um número inteiro positivo arbitrário. Então provamos que [tex3]f(n+1987t) = f(n) + 1987t[/tex3]
o que é bem simples: para [tex3]t=1[/tex3] é verdade (e é verdade para todo [tex3]n[/tex3] ).
Se [tex3]f(n + 1987t) = f(n) + 1987t[/tex3] então colocando [tex3]n+1987[/tex3] no lugar de [tex3]n[/tex3] chegamos em
[tex3]f(n + 1987 +1987t) = f(n+1987) + 1987t = f(n) + 1987 + 1987t[/tex3]
logo a proposição é válida para todo [tex3]t \in \mathbb N[/tex3]
deixe [tex3]1987>s>0 \in \mathbb N[/tex3] e considere o resto [tex3]r[/tex3] da divisão de [tex3]f(s)[/tex3] por [tex3]1987[/tex3] :
[tex3]f(s) = 1987k + r, \,\,\, 0\leq r\ <1987[/tex3]
então [tex3]f(f(s)) = s + 1987 \iff f(1987k + r) = s + 1987 \iff f(r) + 1987k = s + 1987[/tex3] mas [tex3]s<1987[/tex3] por hipótese
[tex3]f(r) + 1987k < 2\cdot 1987 \implies f(r) < 1987(2-k)[/tex3]
então [tex3]k =0[/tex3] ou [tex3]k=1[/tex3] (pois o contradomínio de f é N)
se [tex3]k=1[/tex3] [tex3]f(s) = 1987 + r[/tex3] e [tex3]f(r) =s[/tex3] o link em que eu achei essa solução diz que eventualmente [tex3]s=r[/tex3] mas não explicita o porquê! Isso implicaria um absurdo pois teríamos [tex3]s = 1987 + s \iff 0 =1987[/tex3] parece ter a ver com a paridade par do intervalo [tex3]1,2,3,...,1986[/tex3]
se [tex3]k=0[/tex3] [tex3]f(s) = r[/tex3] e [tex3]f(r) = 1987+s[/tex3] e repete o argumento acima.
Link para a prova em inglês: aqui
Aplique [tex3]n = f(m)[/tex3] então [tex3]f(f(f(m))) = f(m) + 1987[/tex3]
e é claro que [tex3]f(f(f(m))) = f(m+1987)[/tex3]
então a parte da indução é a seguinte:
deixe [tex3]t[/tex3] ser um número inteiro positivo arbitrário. Então provamos que [tex3]f(n+1987t) = f(n) + 1987t[/tex3]
o que é bem simples: para [tex3]t=1[/tex3] é verdade (e é verdade para todo [tex3]n[/tex3] ).
Se [tex3]f(n + 1987t) = f(n) + 1987t[/tex3] então colocando [tex3]n+1987[/tex3] no lugar de [tex3]n[/tex3] chegamos em
[tex3]f(n + 1987 +1987t) = f(n+1987) + 1987t = f(n) + 1987 + 1987t[/tex3]
logo a proposição é válida para todo [tex3]t \in \mathbb N[/tex3]
deixe [tex3]1987>s>0 \in \mathbb N[/tex3] e considere o resto [tex3]r[/tex3] da divisão de [tex3]f(s)[/tex3] por [tex3]1987[/tex3] :
[tex3]f(s) = 1987k + r, \,\,\, 0\leq r\ <1987[/tex3]
então [tex3]f(f(s)) = s + 1987 \iff f(1987k + r) = s + 1987 \iff f(r) + 1987k = s + 1987[/tex3] mas [tex3]s<1987[/tex3] por hipótese
[tex3]f(r) + 1987k < 2\cdot 1987 \implies f(r) < 1987(2-k)[/tex3]
então [tex3]k =0[/tex3] ou [tex3]k=1[/tex3] (pois o contradomínio de f é N)
se [tex3]k=1[/tex3] [tex3]f(s) = 1987 + r[/tex3] e [tex3]f(r) =s[/tex3] o link em que eu achei essa solução diz que eventualmente [tex3]s=r[/tex3] mas não explicita o porquê! Isso implicaria um absurdo pois teríamos [tex3]s = 1987 + s \iff 0 =1987[/tex3] parece ter a ver com a paridade par do intervalo [tex3]1,2,3,...,1986[/tex3]
se [tex3]k=0[/tex3] [tex3]f(s) = r[/tex3] e [tex3]f(r) = 1987+s[/tex3] e repete o argumento acima.
Link para a prova em inglês: aqui
Última edição: Auto Excluído (ID:12031) (Qua 24 Jan, 2018 03:50). Total de 3 vezes.
Jan 2018
24
10:54
Re: (IMO - 1987) Princípio da Indução Finita
Muito obrigada, sousóeu. Eu realmente não entendi muito bem a resolução, mas não porque está mal explicado, muito pelo contrário. Na verdade, faz uns três ou quatro dias que eu estudo esse assunto e, acho que eu ainda não tenho base para compreender completamente a questão. Novamente, obrigada.
-
- Tópicos Semelhantes
- Respostas
- Exibições
- Última msg
-
- 0 Respostas
- 3470 Exibições
-
Última msg por JotaV
-
- 1 Respostas
- 4205 Exibições
-
Última msg por deOliveira
-
- 0 Respostas
- 226 Exibições
-
Última msg por Idocrase
-
- 1 Respostas
- 240 Exibições
-
Última msg por Idocrase