[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Sequência Injetiva

[Anderson Torres]

Nada como uma bijeção N -> Q para encerrar o dia!

Se pensar nas operacoes INC e REV, podemos usar um algoritmo assim:

- Se o número é maior que 1, usa DEC (inversa de INC)
- Se o número é menor que 1, usa INV
- Se o número é 1, pare

Como demonstrar que este procedimento sempre encerrará em 1, não
importando que número racional começou? Acho que no fundo isso é só
uma maneira de encodar fracoes continuas mesmo.

Em ter., 16 de fev. de 2021 às 20:35, Matheus Secco
 escreveu:
>
> Esse problema caiu na Olimpíada Iberoamericana de 2009 que eu participei. Foi 
> o problema 5 da prova e lá pedia para provar injetividade e sobrejetividade.
>
> Em qua, 17 de fev de 2021 00:16, Anderson Torres 
>  escreveu:
>>
>> Em dom., 14 de fev. de 2021 às 17:20, Claudio Buffara
>>  escreveu:
>> >
>> > Será que essa sequência é sobrejetiva (sobre os racionais positivos)?
>> > Porque como a(2^n) = n+1, ela certamente atinge todos os naturais, de modo 
>> > que é ilimitada, superiormente e inferiormente (já que a(2^n + 1) = 
>> > 1/(n+1) ).
>> > Mesmo que não seja, seria interessante descobrir que racionais positivos 
>> > ela não atinge.
>> > É suficiente provar que todos os racionais entre 0 e 1 são atingidos (no 
>> > caso, pelos termos de ordem ímpar), mas não sei se isso facilita.
>> > Vale uma exploração numérica, talvez com uma planilha.
>>
>>
>> Se eu não errei as contas, acredito que sim. Afinal basta reverter a
>> fracao continua.
>>
>> As operacoes parecem ser bem limitadas, contudo nao e necessario muito
>> mais que isso para gerar um racional qualquer:
>>
>> - Função INC: x -> x+1
>> - Função REV: x -> 1/x
>>
>> Talvez haja algum invariante que permita prever que cada operacao esta
>> fadada a cair em 1
>>
>> >
>> >
>> > Abs,
>> > Claudio.
>> >
>> > Enviado do meu iPhone
>> >
>> > Em 14 de fev. de 2021, à(s) 13:57, Anderson Torres 
>> >  escreveu:
>> >
>> > 
>> >
>> >
>> > Em sáb., 13 de fev. de 2021 às 17:56, Jeferson Almir 
>> >  escreveu:
>> >>
>> >> Amigos, peço ajuda em provar a injetividade dessa sequência que seria 
>> >> uma saída para provar a unica ocorrência do racional que aparece nela. 
>> >> Estou andando em círculos tentando montar uma possível indução.
>> >>
>> >>
>> >> Dado a sequência a_1 = 1 e a_2n = a_n  + 1 e a_2n+1 = 1/a_2n.
>> >>
>> >> Prove que para todo racional positivo que ocorre na sequência, ocorre 
>> >> uma única vez.
>> >>
>> >>
>> >
>> > Acho que e uma boa usar fracao continua aqui.
>> >
>> > Se a_n = [c0; c1, c2, ..., ck], temos entao a_1 = [1] e
>> >
>> > a_2n =Â [(1+c0); c1, c2, ..., ck] (chamemos isso de operacao E)
>> > a_2n+1 = [0; (1+c0), c1, c2, ..., ck] (chamemos isso de operacao O)
>> >
>> >
>> > A partir disso, acredito que a bijecao fica quase obvia, bastando 
>> > formalizar algumas inducoes marotas.
>> >
>> > Primeiramente, nenhuma representacao da forma [...,N,1] vai surgir dai a 
>> > partir de a_2. Isso pode ser demonstrado por inducao mesmo: ck=1 somente 
>> > no caso [1], e depois dele a funcao a_n so modifica o comeco da cadeia, 
>> > nunca o final dela.
>> >
>> > Assim sendo, temos certeza que nao tem como um racional aparecer uma vez 
>> > na forma canonica e outra na forma alternativa. E, por conseguinte, se 
>> > duas fracoes tem comprimentos diferentes, elas devem ser diferentes. E 
>> > fracoes com comprimentos iguais diferem se e somente se pelo menos um dos 
>> > componentes diferir.
>> >
>> > Agora, a funcao recursiva age de duas formas. Uma delas altera o 
>> > comprimento em 1, e a outra mantém. A que altera, só altera 
>> > acrescentando o 0 na cabeceira. A que não altera, incrementa a cabeceira.
>> >
>> > Desta forma, é possível gerar de maneira unica qualquer numero racional 
>> > comecando do 1.
>> >
>> > - Qualquer fracao de comprimento 1 pode ser gerada simplesmente aplicando 
>> > a operacao E tantas vezes quantas forem necessarias. E tambem nao e 
>> > possivel fazer isso de outra maneira, pois a operacao O aumentara o 
>> > comprimento de maneira irreversivel.
>> >
>> > - Dada uma fracao com comprimento K, temos duas sub inducoes para fazer:
>> >
>> > + A fracao tem comprimento K e comeca com 0.
>> >
>> > Â  Entao ela foi gerada por uma operacao O. O elemento que a gerou tinha 
>> > menos componentes, os quais satisfazem a hipotese de inducao.
>> >
>> > + A fracao tem comprimento K e comeca com algo maior que 0.
>> >
>> > Entao ela foi gerada por uma operacao E. A fracao da qual ela foi gerada 
>> > difere unicamente no primeiro elemento, o qual antes era menor. Assim 
>> > sendo, e possivel reduzir isso ate chegar no caso anterior.
>> >
>> > E isso demonstra recursivamente a unicidade e existencia!
>> >
>> >
>> >
>> >> --
>> >> 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 

[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Sequência Injetiva

[Matheus Secco]

Esse problema caiu na Olimpíada Iberoamericana de 2009 que eu participei.
Foi o problema 5 da prova e lá pedia para provar injetividade e
sobrejetividade.

Em qua, 17 de fev de 2021 00:16, Anderson Torres <
torres.anderson...@gmail.com> escreveu:

> Em dom., 14 de fev. de 2021 às 17:20, Claudio Buffara
>  escreveu:
> >
> > Será que essa sequência é sobrejetiva (sobre os racionais positivos)?
> > Porque como a(2^n) = n+1, ela certamente atinge todos os naturais, de
> modo que é ilimitada, superiormente e inferiormente (já que a(2^n + 1) =
> 1/(n+1) ).
> > Mesmo que não seja, seria interessante descobrir que racionais positivos
> ela não atinge.
> > É suficiente provar que todos os racionais entre 0 e 1 são atingidos (no
> caso, pelos termos de ordem ímpar), mas não sei se isso facilita.
> > Vale uma exploração numérica, talvez com uma planilha.
>
>
> Se eu não errei as contas, acredito que sim. Afinal basta reverter a
> fracao continua.
>
> As operacoes parecem ser bem limitadas, contudo nao e necessario muito
> mais que isso para gerar um racional qualquer:
>
> - Função INC: x -> x+1
> - Função REV: x -> 1/x
>
> Talvez haja algum invariante que permita prever que cada operacao esta
> fadada a cair em 1
>
> >
> >
> > Abs,
> > Claudio.
> >
> > Enviado do meu iPhone
> >
> > Em 14 de fev. de 2021, à(s) 13:57, Anderson Torres <
> torres.anderson...@gmail.com> escreveu:
> >
> > 
> >
> >
> > Em sáb., 13 de fev. de 2021 às 17:56, Jeferson Almir <
> jefersonram...@gmail.com> escreveu:
> >>
> >> Amigos, peço ajuda em provar a injetividade dessa sequência que seria
> uma saída para provar a unica ocorrência do racional que aparece nela.
> Estou andando em círculos tentando montar uma possível indução.
> >>
> >>
> >> Dado a sequência a_1 = 1 e a_2n = a_n  + 1 e a_2n+1 = 1/a_2n.
> >>
> >> Prove que para todo racional positivo que ocorre na sequência, ocorre
> uma única vez.
> >>
> >>
> >
> > Acho que e uma boa usar fracao continua aqui.
> >
> > Se a_n = [c0; c1, c2, ..., ck], temos entao a_1 = [1] e
> >
> > a_2n =Â [(1+c0); c1, c2, ..., ck] (chamemos isso de operacao E)
> > a_2n+1 = [0; (1+c0), c1, c2, ..., ck] (chamemos isso de operacao O)
> >
> >
> > A partir disso, acredito que a bijecao fica quase obvia, bastando
> formalizar algumas inducoes marotas.
> >
> > Primeiramente, nenhuma representacao da forma [...,N,1] vai surgir dai a
> partir de a_2. Isso pode ser demonstrado por inducao mesmo: ck=1 somente
> no caso [1], e depois dele a funcao a_n so modifica o comeco da cadeia,
> nunca o final dela.
> >
> > Assim sendo, temos certeza que nao tem como um racional aparecer uma vez
> na forma canonica e outra na forma alternativa. E, por conseguinte, se duas
> fracoes tem comprimentos diferentes, elas devem ser diferentes. E fracoes
> com comprimentos iguais diferem se e somente se pelo menos um dos
> componentes diferir.
> >
> > Agora, a funcao recursiva age de duas formas. Uma delas altera o
> comprimento em 1, e a outra mantém. A que altera, só altera acrescentando
> o 0 na cabeceira. A que não altera, incrementa a cabeceira.
> >
> > Desta forma, é possível gerar de maneira unica qualquer numeroÂ
> racional comecando do 1.
> >
> > - Qualquer fracao de comprimento 1 pode ser gerada simplesmente
> aplicando a operacao E tantas vezes quantas forem necessarias. E tambem
> nao e possivel fazer isso de outra maneira, pois a operacao O aumentara o
> comprimento de maneira irreversivel.
> >
> > - Dada uma fracao com comprimento K, temos duas sub inducoes para fazer:
> >
> > + A fracao tem comprimento K e comeca com 0.
> >
> > Â  Entao ela foi gerada por uma operacao O. O elemento que a gerou tinha
> menos componentes, os quais satisfazem a hipotese de inducao.
> >
> > + A fracao tem comprimento K e comeca com algo maior que 0.
> >
> > Entao ela foi gerada por uma operacao E. A fracao da qual ela foi gerada
> difere unicamente no primeiro elemento, o qual antes era menor. Assim
> sendo, e possivel reduzir isso ate chegar no caso anterior.
> >
> > E isso demonstra recursivamente a unicidade e existencia!
> >
> >
> >
> >> --
> >> 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.
>
>
> =
> 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] Re: [obm-l] Sequência Injetiva

[Claudio Buffara]

a(1) = 1
a(2n) = a(2n-1) + 1
a(2n+1) = 1/a(2n)

Fazendo a(n) = p(n)/q(n), obtemos duas sequências: p(n) e q(n).
E elas são tais que:
p(1) = q(1) = 1
p(2n) = p(2n-1) + q(2n-1)
q(2n) = q(2n-1)
p(2n+1) = q(2n)
q(2n+1) = p(2n)

Como as sequências começam com 1 e 1, que são primos entre si, e como
mdc(p,q) = mdc(q,p) = mdc(p+q,q), p(n) e q(n) sempre serão primos entre si.

Usando a definição de p e q:
p(2n+1) = q(2n) = q(2n-1) = p(2n-2) = p(2n-3) + q(2n-3) = p(2n-3) + q(2n-2)
= p(2n-3) + p(2n-1)
e
p(2n+2) = p(2n+1) + q(2n+1) = q(2n) + p(2n) = q(2n-1) + p(2n) = p(2n-2) +
p(2n)

Ou seja, os termos p(n) de ordem ímpar e de ordem par realmente formam uma
sequência de Fibonacci.
Os de ordem ímpar começam com p(1) = p(3) = 1 e os de ordem par com p(2) =
2 e p(4) = 3.

[]s,
Claudio.

On Sun, Feb 14, 2021 at 10:03 AM Claudio Buffara 
wrote:

> Ué!  Continua sendo. Só que é outra questão...
>
>
> On Sun, Feb 14, 2021 at 3:34 AM Ralph Costa Teixeira 
> wrote:
>
>> Sim, voce tem razao -- eu achei que era a_2n = a_{2n-1} +1. Que pena, era
>> uma boa questao com Fibonacci. :)
>>
>> On Sun, Feb 14, 2021 at 12:35 AM Claudio Buffara <
>> claudio.buff...@gmail.com> wrote:
>>
>>> Oi, Ralph:
>>>
>>> Eu posso ter entendido errado a definição da sequência, mas achei termos
>>> diferentes dos seus:
>>> 1:  1
>>> 2:  2
>>> 3:  1/2
>>> 4:  3
>>> 5:  1/3
>>> 6:  3/2
>>> 7:  2/3
>>> 8:  4
>>> 9:  1/4
>>> 10:  4/3
>>> 11:  3/4
>>> 12:  5/2
>>> 13:  2/5
>>> 14:  5/3
>>> 15:  3/5
>>> 16:  5
>>> ...
>>>
>>> []s,
>>> Claudio.
>>>
>>>
>>> On Sat, Feb 13, 2021 at 7:59 PM Ralph Costa Teixeira 
>>> wrote:
>>>
 Meio enrolado, vou escrever meio vagamente.

 Eu sugiro olhar primeiro para os caras com indice impar. Sao eles:
 a1=1/1
 a3=1/2
 a5=2/3
 a7=3/5
 a8=5/8
 ...
 Ou seja, mostre que eles sao quocientes de numeros de Fibonacci
 consecutivos (os caras de indice par sao os inversos desses). Agora tem
 varias maneiras de continuar:

 -- Voce pode mostrar que os numeros de Fibonacci consecutivos sao
 primos entre si; portanto cada fracao dessas fica unicamente determinada
 por numerador e denominador, e (como os numeros de Fibonacci formam uma
 sequencia crescente) vao ser distintos entre si;
 -- Se voce nao quiser entrar no merito do Fibonacci, tente mostrar
 (pode ser por inducao) que a3 < a7 < a11 <...>>> a_(4k+1) < ... < a13 < a9 < a5 < 1  (phi ali seria (raiz(5)-1) / 2, acho).

 De qualquer forma, como a_(2n+1)<1, a1=1 e os "a_2n" sao os inversos
 dos "a_2n+1, vao ser todos diferentes.

 Abraco, Ralph.


 On Sat, Feb 13, 2021 at 5:56 PM Jeferson Almir <
 jefersonram...@gmail.com> wrote:

> Amigos, peço ajuda em provar a injetividade dessa sequência que seria
> uma saída para provar a unica ocorrência do racional que aparece nela.
> Estou andando em círculos tentando montar uma possível indução.
>
>
> Dado a sequência a_1 = 1 e a_2n = a_n  + 1 e a_2n+1 = 1/a_2n.
>
> Prove que para todo racional positivo que ocorre na sequência, ocorre
> uma única vez.
>
> --
> 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.

[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Sequência Injetiva

[Claudio Buffara]

Ué!  Continua sendo. Só que é outra questão...


On Sun, Feb 14, 2021 at 3:34 AM Ralph Costa Teixeira 
wrote:

> Sim, voce tem razao -- eu achei que era a_2n = a_{2n-1} +1. Que pena, era
> uma boa questao com Fibonacci. :)
>
> On Sun, Feb 14, 2021 at 12:35 AM Claudio Buffara <
> claudio.buff...@gmail.com> wrote:
>
>> Oi, Ralph:
>>
>> Eu posso ter entendido errado a definição da sequência, mas achei termos
>> diferentes dos seus:
>> 1:  1
>> 2:  2
>> 3:  1/2
>> 4:  3
>> 5:  1/3
>> 6:  3/2
>> 7:  2/3
>> 8:  4
>> 9:  1/4
>> 10:  4/3
>> 11:  3/4
>> 12:  5/2
>> 13:  2/5
>> 14:  5/3
>> 15:  3/5
>> 16:  5
>> ...
>>
>> []s,
>> Claudio.
>>
>>
>> On Sat, Feb 13, 2021 at 7:59 PM Ralph Costa Teixeira 
>> wrote:
>>
>>> Meio enrolado, vou escrever meio vagamente.
>>>
>>> Eu sugiro olhar primeiro para os caras com indice impar. Sao eles:
>>> a1=1/1
>>> a3=1/2
>>> a5=2/3
>>> a7=3/5
>>> a8=5/8
>>> ...
>>> Ou seja, mostre que eles sao quocientes de numeros de Fibonacci
>>> consecutivos (os caras de indice par sao os inversos desses). Agora tem
>>> varias maneiras de continuar:
>>>
>>> -- Voce pode mostrar que os numeros de Fibonacci consecutivos sao primos
>>> entre si; portanto cada fracao dessas fica unicamente determinada por
>>> numerador e denominador, e (como os numeros de Fibonacci formam uma
>>> sequencia crescente) vao ser distintos entre si;
>>> -- Se voce nao quiser entrar no merito do Fibonacci, tente mostrar (pode
>>> ser por inducao) que a3 < a7 < a11 <...>> < ... < a13 < a9 < a5 < 1  (phi ali seria (raiz(5)-1) / 2, acho).
>>>
>>> De qualquer forma, como a_(2n+1)<1, a1=1 e os "a_2n" sao os inversos dos
>>> "a_2n+1, vao ser todos diferentes.
>>>
>>> Abraco, Ralph.
>>>
>>>
>>> On Sat, Feb 13, 2021 at 5:56 PM Jeferson Almir 
>>> wrote:
>>>
 Amigos, peço ajuda em provar a injetividade dessa sequência que seria
 uma saída para provar a unica ocorrência do racional que aparece nela.
 Estou andando em círculos tentando montar uma possível indução.


 Dado a sequência a_1 = 1 e a_2n = a_n  + 1 e a_2n+1 = 1/a_2n.

 Prove que para todo racional positivo que ocorre na sequência, ocorre
 uma única vez.

 --
 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.

[obm-l] Re: [obm-l] Re: [obm-l] Re: [obm-l] Sequência Injetiva

[Ralph Costa Teixeira]

Sim, voce tem razao -- eu achei que era a_2n = a_{2n-1} +1. Que pena, era
uma boa questao com Fibonacci. :)

On Sun, Feb 14, 2021 at 12:35 AM Claudio Buffara 
wrote:

> Oi, Ralph:
>
> Eu posso ter entendido errado a definição da sequência, mas achei termos
> diferentes dos seus:
> 1:  1
> 2:  2
> 3:  1/2
> 4:  3
> 5:  1/3
> 6:  3/2
> 7:  2/3
> 8:  4
> 9:  1/4
> 10:  4/3
> 11:  3/4
> 12:  5/2
> 13:  2/5
> 14:  5/3
> 15:  3/5
> 16:  5
> ...
>
> []s,
> Claudio.
>
>
> On Sat, Feb 13, 2021 at 7:59 PM Ralph Costa Teixeira 
> wrote:
>
>> Meio enrolado, vou escrever meio vagamente.
>>
>> Eu sugiro olhar primeiro para os caras com indice impar. Sao eles:
>> a1=1/1
>> a3=1/2
>> a5=2/3
>> a7=3/5
>> a8=5/8
>> ...
>> Ou seja, mostre que eles sao quocientes de numeros de Fibonacci
>> consecutivos (os caras de indice par sao os inversos desses). Agora tem
>> varias maneiras de continuar:
>>
>> -- Voce pode mostrar que os numeros de Fibonacci consecutivos sao primos
>> entre si; portanto cada fracao dessas fica unicamente determinada por
>> numerador e denominador, e (como os numeros de Fibonacci formam uma
>> sequencia crescente) vao ser distintos entre si;
>> -- Se voce nao quiser entrar no merito do Fibonacci, tente mostrar (pode
>> ser por inducao) que a3 < a7 < a11 <...> < ... < a13 < a9 < a5 < 1  (phi ali seria (raiz(5)-1) / 2, acho).
>>
>> De qualquer forma, como a_(2n+1)<1, a1=1 e os "a_2n" sao os inversos dos
>> "a_2n+1, vao ser todos diferentes.
>>
>> Abraco, Ralph.
>>
>>
>> On Sat, Feb 13, 2021 at 5:56 PM Jeferson Almir 
>> wrote:
>>
>>> Amigos, peço ajuda em provar a injetividade dessa sequência que seria
>>> uma saída para provar a unica ocorrência do racional que aparece nela.
>>> Estou andando em círculos tentando montar uma possível indução.
>>>
>>>
>>> Dado a sequência a_1 = 1 e a_2n = a_n  + 1 e a_2n+1 = 1/a_2n.
>>>
>>> Prove que para todo racional positivo que ocorre na sequência, ocorre
>>> uma única vez.
>>>
>>> --
>>> 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.