[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Função Composta

[Bruno Visnadi]

Realmente eu me expressei mal ali. Eu quis dizer que o menor N deve ser 1,
2 ou 5.

Em 13 de maio de 2018 21:22, Jeferson Almir 
escreveu:

> Boa noite.
> Eu só não entendi essa passagem
>  “ Para todo a, queremos que N seja igual a 1, 2 ou 5 (os divisores de 50
> menores ou iguais a 5).“
> Pois pra mim eu teria que levar em conta somente os divisores de 50
>
> Em dom, 13 de mai de 2018 às 19:43, Bruno Visnadi <
> brunovisnadida...@gmail.com> escreveu:
>
>> Não sei se ficou meio confuso:
>> De fato a função é injetiva, pois se f(a) = f(b) então f^50(a) = f^50(b)
>> e a = b. E claramente é sobrejetiva, portanto, é bijetiva. Existem 5! = 120
>> bijeções de S em S. Vamos descontar as que não tem a propriedade desejada.
>> Em cada bijeção de S em S, dado um a, existe um menor N tal que f^N(a) =
>> a. Para todo a, queremos que N seja igual a 1, 2 ou 5 (os divisores de 50
>> menores ou iguais a 5).
>> Se existem um a cujo N é igual a 3, temos um caso em que f(a) = b, f(b)
>> = c e f(c) = a . Existem 10 maneiras de escolher a, b, c de S, duas
>> maneiras de escolher o 'ciclo' entre eles (a->b->c ou a->c->b), e mais 2
>> maneiras de escolher a imagem dos outros 2 elementos (se forem x e y,
>> podemos ter f(x) = x e f(y) = y ou f(x) = y e f(y) = x). Então temos 10*2*2
>> = 40 funções deste tipo.
>> Se existe um a cujo N é igual a 4, temos um caso em que f(a) = b, f(b) =
>> c e f(c) = d e f(d) = a. Temos 5 maneiras de escolher estes 4 elementos de
>> S, e mais 6 maneiras de ordenar o 'ciclo' entre eles (basta fixar um deles
>> e vemos que são 3! maneiras). Então 6*5 = 30 funções deste tipo.
>> Logo a quantidade de funções com as propriedades que buscamos é 120-40-30
>> = 50.
>>
>> Em 13 de maio de 2018 18:03, Jeferson Almir 
>> escreveu:
>>
>>> Seja S = { 1,2,3,4,5 }, quantas são as funções de f: S -> S tais que
>>> f^50(x)= x para todo x pertencente a S ?? ( f^50(x) = fofofo...of(x)
>>> Eu provei que ela era injetiva e acho que provei também que ela era
>>> sobrejetiva mas minha resposta dar 45 . O gabarito diz que são 50. Desde já
>>> agradeço qualquer ajuda.
>>>
>>> --
>>> Esta mensagem foi verificada pelo sistema de antivírus e
>>> acredita-se estar livre de perigo.
>>
>>
>> --
>> Esta mensagem foi verificada pelo sistema de antivírus e
>> acredita-se estar livre de perigo.
>
>
> --
> Esta mensagem foi verificada pelo sistema de antivírus e
> acredita-se estar livre de perigo.
>

-- 
Esta mensagem foi verificada pelo sistema de antiv�rus e
 acredita-se estar livre de perigo.

[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Função Composta

[Jeferson Almir]

Valeu Raph e os demais. Aprendi muito com vcs!!

Em sáb, 12 de mai de 2018 às 20:25, Ralph Teixeira 
escreveu:

> Oops, eh verdade, esqueci de mostrar que f nao tem ponto fixo em Z_2005
> (obviamente f nao tem ponto fixo, pois f(f(a))<>a).
>
> Suponha por absurdo que f(a)=a+K.2005 para algum a em {0,1,...2004}, com K
> natural. Entao f(a+K.2005)=f(f(a))=a+2005. Agora, usando nossa
> propriedadezinha:
>
> f(a+K.2005)-f(a)=K.2005
> a+2005 - (a+K.2005) = K.2005
> K = 1/2 (absurdo).
>
> Abraco, Ralph.
>
>
>
> 2018-05-12 2:49 GMT-03:00 Bernardo Freitas Paulo da Costa <
> bernardo...@gmail.com>:
>
>> Oi Ralph,
>>
>> 2018-05-11 20:03 GMT-03:00 Ralph Teixeira :
>> > (Vou supor que 0 eh natural; se nao for, apenas troque 0 por 2005 ali
>> > embaixo e ajeite as coisas)
>> >
>> > Primeiro: f eh injetiva. De fato, f(a)=f(b) => f(f(a))=f(f(b)) =>
>> > a+2005=b+2005 => a=b.
>> >
>> > Segundo: para todo n natural, f(n+2005)=f(f(f(n)))=f(n)+2005. Portanto,
>> por
>> > indução, para qualquer K natural, tem-se
>> > f(n+K.2005)=f(n)+K.2005, ou seja, f(n+K.2005)-f(n)=K.2005.
>> >
>> > VERSÃO CURTA COM TERMINOLOGIA "MOD":
>> > Ou seja, mostramos que   a=b (mod 2005) => f(a)=f(b) (mod 2005).
>> > Agora, se f(m)=n (mod 2005), entao f(n)=f(f(m))=m+2005=m (mod 2005). Ou
>> > seja, f estah bem definida e eh sua propria inversa em Z_2005, o que eh
>> > absurdo, pois Z_2005 tem um numero impar de elementos.
>>
>> Peraí, não entendi direito... se f(n) == n (mod 2005), temos uma
>> função que é sua própria inversa mod 2005.  Temos que excluir este
>> caso...
>>
>> > 2018-05-11 10:42 GMT-03:00 Jeferson Almir :
>> >>
>> >> Como provar que nos naturais não existe a função f ( f(n) ) = n + 2005
>> ???
>> >>
>>
>> Abraços,
>> --
>> Bernardo Freitas Paulo da Costa
>>
>> --
>> Esta mensagem foi verificada pelo sistema de antivírus e
>>  acredita-se estar livre de perigo.
>>
>>
>> =
>> Instru�ões para entrar na lista, sair da lista e usar a lista em
>> http://www.mat.puc-rio.br/~obmlistas/obm-l.html
>> =
>>
>
>
> --
> Esta mensagem foi verificada pelo sistema de antivírus e
> acredita-se estar livre de perigo.

-- 
Esta mensagem foi verificada pelo sistema de antiv�rus e
 acredita-se estar livre de perigo.

[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Função Composta

[Ralph Teixeira]

Oops, eh verdade, esqueci de mostrar que f nao tem ponto fixo em Z_2005
(obviamente f nao tem ponto fixo, pois f(f(a))<>a).

Suponha por absurdo que f(a)=a+K.2005 para algum a em {0,1,...2004}, com K
natural. Entao f(a+K.2005)=f(f(a))=a+2005. Agora, usando nossa
propriedadezinha:

f(a+K.2005)-f(a)=K.2005
a+2005 - (a+K.2005) = K.2005
K = 1/2 (absurdo).

Abraco, Ralph.



2018-05-12 2:49 GMT-03:00 Bernardo Freitas Paulo da Costa <
bernardo...@gmail.com>:

> Oi Ralph,
>
> 2018-05-11 20:03 GMT-03:00 Ralph Teixeira :
> > (Vou supor que 0 eh natural; se nao for, apenas troque 0 por 2005 ali
> > embaixo e ajeite as coisas)
> >
> > Primeiro: f eh injetiva. De fato, f(a)=f(b) => f(f(a))=f(f(b)) =>
> > a+2005=b+2005 => a=b.
> >
> > Segundo: para todo n natural, f(n+2005)=f(f(f(n)))=f(n)+2005. Portanto,
> por
> > indução, para qualquer K natural, tem-se
> > f(n+K.2005)=f(n)+K.2005, ou seja, f(n+K.2005)-f(n)=K.2005.
> >
> > VERSÃO CURTA COM TERMINOLOGIA "MOD":
> > Ou seja, mostramos que   a=b (mod 2005) => f(a)=f(b) (mod 2005).
> > Agora, se f(m)=n (mod 2005), entao f(n)=f(f(m))=m+2005=m (mod 2005). Ou
> > seja, f estah bem definida e eh sua propria inversa em Z_2005, o que eh
> > absurdo, pois Z_2005 tem um numero impar de elementos.
>
> Peraí, não entendi direito... se f(n) == n (mod 2005), temos uma
> função que é sua própria inversa mod 2005.  Temos que excluir este
> caso...
>
> > 2018-05-11 10:42 GMT-03:00 Jeferson Almir :
> >>
> >> Como provar que nos naturais não existe a função f ( f(n) ) = n + 2005
> ???
> >>
>
> Abraços,
> --
> Bernardo Freitas Paulo da Costa
>
> --
> Esta mensagem foi verificada pelo sistema de antivírus e
>  acredita-se estar livre de perigo.
>
>
> =
> Instru�ões para entrar na lista, sair da lista e usar a lista em
> http://www.mat.puc-rio.br/~obmlistas/obm-l.html
> =
>

-- 
Esta mensagem foi verificada pelo sistema de antiv�rus e
 acredita-se estar livre de perigo.

[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Função Composta

[Bruno Visnadi]

 Vou considerar que 0 é natural (para N = {1, 2, 3...} a prova é análoga).
Lema 1: f é injetora.
Prova: Se f(a) = f(b) então f(f(a)) = f(f(b)) e a = b.
Lema 2: Se f(a) > 2004, então a está na imagem de f.
Prova: Se f(a) > 2004, então f(f(f(a) - 2005)) = f(a). Como a função é
injetora, f(f(a) - 2005) = a.
Suponha que existe uma função f, N -> N, tal que f(f(n)) = n + 2005.
Seja S o conjunto dos 2005 naturais [0, 2004]. Suponha que existam 1003
elementos t de S tais que f(t) ∈ S. Portanto, há no máximo 1002 elementos t
de S tais que f(t) ∉ S. Assim, uma vez que a função é injetora, pelo
princípio das casas dos pombos haveria um elemento t tal que f(f(t)) ∈ S ⇒
2015 + t  ∈ S, absurdo, pois 2005 + t > 2004.

Então existem pelo menos 1003 elementos t de S com f(t) > 2004. Sejam a1,
a2 (...) a1003 tais elementos. Pelo Lema 2, estes números estão na imagem
de f. Então existem 1003 números b1, b2, (...) b1003 tais que f(b1) = a1,
f(b2) = a2, (...) f(b1003) = a1003. Não podem haver i e j tais que bi = aj,
pois f(bi) < 2005 e f(aj) > 2004. Assim, se bi ∈ S, bi é um dos 1002
elementos t de S com f(t) ∈ S. Mas existem 1003 números bi, portanto, ao
menos um deles não pertence a S. Seja bk tal elemento, com f(bk) = ak. Pelo
Lema 2, bk está na imagem de f, então existe c com f(c) = bk ⇒ f(f(c)) =
f(bk) ⇒ 2005 + c = ak. Absurdo, pois ak < 2005.

Portanto, não existe tal f.

Em 11 de maio de 2018 18:46, Rodrigo Ângelo 
escreveu:

> acho que, de forma mais geral, não pode existir nenhuma f: |N -> |N, tal
> que f(f(n)) = n*p(n) + i, onde g(n) seja qualquer polinômio natural de n e
> i é um número ímpar
>
> On Fri, May 11, 2018 at 6:37 PM Rodrigo Ângelo 
> wrote:
>
>> Se f não for polinomial, então f deve ser da forma f(n) = g(n) + m, onde
>> g(n) é uma função não polinomial de n e m é um natural ou zero
>> f(f(n)) = g(f(n)) + m
>>
>> Com f(f(n)) = n + 2005, teríamos
>> g(f(n)) + m = n  + 2005
>> g(f(n)) = n  + 2005 - m onde m é uma constante natural então g(f(n)) é um
>> polinômio, que é um absurdo.
>>
>> On Fri, May 11, 2018 at 6:20 PM Rodrigo Ângelo 
>> wrote:
>>
>>> Se f for qualquer polinômio de grau maior que 1 então f(f(n)) também é
>>> um polinomio maior que 1. Daí já dá pra eliminar toda f polinomial
>>>
>>> On Fri, May 11, 2018 at 6:15 PM Julio César Saldaña Pumarica <
>>> saldana...@pucp.edu.pe> wrote:
>>>
 com isso prova que f nao pode ser linear mas o enunciado pareces mais
 geral

 El viernes, 11 de mayo de 2018, Rodrigo Ângelo 
 escribió:

> Se f : |N -> |N, f(n) = an + m, com a e m constantes naturais, então
> teríamos
> f(f(n)) = a(an + m) + m
> f(f(n)) = (a^2)n + am + m
>
> Com f(f(n)) = n + 2005, teríamos a = 1 e m = 2005/2, absurdo, pois m
> deve ser um número natural.
>
> On Fri, May 11, 2018 at 10:51 AM Jeferson Almir <
> jefersonram...@gmail.com> wrote:
>
>> Como provar que nos naturais não existe a função f ( f(n) ) = n +
>> 2005 ???
>>
>> --
>> Esta mensagem foi verificada pelo sistema de antivírus e
>> acredita-se estar livre de perigo.
>
>
> --
> Esta mensagem foi verificada pelo sistema de antivírus e
> acredita-se estar livre de perigo.


 --
 Esta mensagem foi verificada pelo sistema de antivírus e
 acredita-se estar livre de perigo.
>>>
>>>
> --
> Esta mensagem foi verificada pelo sistema de antivírus e
> acredita-se estar livre de perigo.
>

-- 
Esta mensagem foi verificada pelo sistema de antiv�rus e
 acredita-se estar livre de perigo.