Oi, Shine:
Obrigado pela dica. Eu realmente nao tinha percebido que f(Fib(n)) = Fib(n+1).
O resultado que voce menciona sobre os irracionais x e y com 1/x + 1/y = 1 chama-se Teorema de Beatty. Uma demonstracao razoavelmente simples pode ser encontrada on-line em:
(alias, este eh um site sobre matematica com varios artigos bem interessantes e relevantes para olimpiadas)
O caso particular (x = phi e y = phi^2) foi um problema proposto na Eureka 15, se nao me engano.
Vou tentar demonstrar as relacoes:
f([n*phi]+1) = [n*phi^2]+1 e f([n*phi^2]+1) = [n*phi]+1
De qualquer jeito, tenho que admitir que a conexao involucao-Fibonacci-Beatty eh extrememente nao-trivial (pelo menos pra mim).
Um abraco,
Claudio.
| De: |
owner-obm-l@sucuri.mat.puc-rio.br |
| Para: |
obm-l@mat.puc-rio.br |
| Data: |
Sat, 2 Aug 2003 13:46:35 -0700 (PDT) |
| Assunto: |
Re: [obm-l] Involucao_de_N_em_N |
> 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
> =========================================================================
>
>