Mostre que não existe uma função [tex3]f:\mathbb{N}\rightarrow \mathbb{N}[/tex3]
tal que [tex3]f(f(n))=n+1987,\ \forall \ n\ \in \ \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.
Olimpíadas ⇒ (IMO - 1987) Princípio da Indução Finita Tópico resolvido
-
GiovanaM
- Mensagens: 5
- Registrado em: 24 Jan 2018, 00:26
- Última visita: 26-01-18
- Agradeceram: 2 vezes
Jan 2018
24
00:55
(IMO - 1987) Princípio da Indução Finita
Editado pela última vez por GiovanaM em 24 Jan 2018, 10:51, em um total de 1 vez.
-
Auto Excluído (ID:12031)
- Ú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
Editado pela última vez por Auto Excluído (ID:12031) em 24 Jan 2018, 03:50, em um total de 3 vezes.
-
GiovanaM
- Mensagens: 5
- Registrado em: 24 Jan 2018, 00:26
- Última visita: 26-01-18
- Agradeceram: 2 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
- Resp.
- Exibições
- Últ. msg
-
- 1 Resp.
- 1146 Exibições
-
Últ. msg por fabit
-
- 1 Resp.
- 598 Exibições
-
Últ. msg por jedi
-
- 2 Resp.
- 1447 Exibições
-
Últ. msg por rodBR
-
- 4 Resp.
- 2345 Exibições
-
Últ. msg por MatheusBorges
-
- 4 Resp.
- 1282 Exibições
-
Últ. msg por Andre13000
