Re: [obm-l] Involucao_de_N_em_N

[Carlos Gustavo Tamm de Araujo Moreira <gugu@xxxxxxx>]

   Caro Shine,
   Na verdade eu fiquei sabendo desse problema pela lista mesmo (se nao me
engano proposto pelo Claudio Buffara) e sugeri que fosse incluido numa lista 
de treinamento para a IMO. E' bem legal, nao ?
   Abracos,
            Gugu
 
>
>Oi,
>
>Esse problema é de uma lista da preparação para a IMO
>desse ano e, se não me engano, o Gugu o propôs (é isso
>mesmo, Gugu?). A preparação desse ano já foi, então
>podemos conversar sobre esse problema.
>
>Vamos ver alguns valores pequenos:
>
>f(1) = 1;
>f(2) = 3;
>f(3) = 2;
>f(4) = 6;
>f(5) = 8;
>f(6) = 4;
>f(7) = 11;
>f(8) = 5;
>f(9) = 14;
>f(10) = 15;
>f(11) = 7;
>f(12) = 19;
>f(13) = 21...
>
>Vamos formar os pares (a,b) nas quais f(a) = b e f(b)
>= a (vamos convencionar a < b):
>
>(1;1), (2;3), (4;6), (5;8), (7;11), (9;14), (10;15),
>(12;19), (13;21)...
>
>Apareceram os números consecutivos de Fibonacci (1;1),
>(2;3), (5;8) e (13;21)... e as razões b/a em cada par
>são muito próximas... de phi = (1+raiz(5))/2!
>
>Pode-se provar que se x e y são irracionais tais que
>1/x + 1/y = 1 então as seqüências [mx] e [ny], m,n
>inteiros positivos, e [r] é o maior inteiro menor ou
>igual a r, particionam os inteiros positivos, ou seja,
>{[mx]} união {[ny]} = Z+* e {[mx]} inter {[ny]} =
>vazio (eu aprendi a demonstração desse fato no livro
>"Elementary Number Theory", de Joe Roberts). phi e
>phi^2 satisfazem essa condição, assim as seqüências
>[m*phi] e [n*phi^2] particionam Z+*.
>
>Se você calcular os valores pequenos dessas duas
>seqüências, pode conjecturar que f([n*phi]+1) =
>[n*phi^2]+1 e f([n*phi^2]+1) = [n*phi]+1.
>
>Eu lembro que, na época, provei isso por indução,
>adicionando algumas hipóteses para sair mais fácil...
>
>Um problema relacionado caiu na IMO 1993 (acho que o
>ano é esse...): Encontre uma função f de N em N tal
>que f(f(n)) = f(n) + n para todo n em N.
>
>[]'s
>Shine
>
>> Caros colegas:
>
>> Este problema me foi proposto ha alguns meses pelo
>Domingos Jr. mas eu nao consegui fazer. Trata-se da
>generalizacao de um problema que ele resolveu aqui na
>lista.
>
>> Seja N = conjunto dos inteiros positivos.
>> 
>> Definimos f:N --> N por:
>> f(1) = 1
>> e, para n > 1,
>> f(n) = menor inteiro positivo que:
>> i)  nao pertence a {f(1), ...., f(n-1)}
>> e
>> ii) faz com que [f(1) + ... + f(n)]/n seja inteiro.
>> 
>> Prove que f eh uma involucao, ou seja, eh tal que
>f(f(n)) = n, para todo n em N. (em particular, isso
>implica que f eh uma bijecao, que foi o que o Domingos
>provou).
>
>> Qualquer ajuda serah bem-vinda.
>
>> Um abraco,
>> Claudio.
>
>__________________________________
>Do you Yahoo!?
>Yahoo! SiteBuilder - Free, easy-to-use web site design software
>http://sitebuilder.yahoo.com
>=========================================================================
>Instruções para entrar na lista, sair da lista e usar a lista em
>http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
>=========================================================================

=========================================================================
Instruções para entrar na lista, sair da lista e usar a lista em
http://www.mat.puc-rio.br/~nicolau/olimp/obm-l.html
=========================================================================