Re: [obm-l] Involucao_de_N_em_N

[Carlos Yuzo Shine <cyshine@xxxxxxxxx>]

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