Re: [obm-l] ajuda

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

on 26.01.05 13:39, plataoterra at plataoterra@ig.com.br wrote:

> Olá! 
> 
> Gostaria de pedir ajuda em uma questão que caiu no segundo teste de
> seleção para a 40° IMO e 14° IBERO.
> 
> "Problema 6 
> 
> Seja F_n o conjunto de todas as bijeções f de {1,...,n} em {1,...,n}
> satisfazendo 
> a)f(k)<k+2 para k=1,...,n e
> b)f(k) diferente de k para k=1,...,n.
> 
> Determine a probabilidade de que f(1) diferente de 1 para um f
> arbitrário em F_n."
> 
Do jeito que voce escreveu, a probabilidade eh 1 pois, por definicao, todos
os elementos de F_n sao permutacoes caoticas (bijecoes sem ponto fixo). Em
particular, f(1) <> 1, para todo f de F_n.

> Eu tentei fazê-la para n's pequenos (até 5) e a probabilidade encontrada é
> dada em função da sequência de Fibonacci. Considerando que
> i) F_0=0; 
> ii) F_n+2=F_n+1 + F_n.
> 
> a probabilidade conjecturada para F_n seria
> F_n-1/F_n 
> só que não consegui demonstrar nada disso. Parece que li que quando n tende
> ao infinito, essa probabilidade fica muito próxima de (sqrt(5)-1)/2, que é o
> inverso da razão áurea( acho).
> 
> Veja: 
> Para n=1 
> f(1)=1. Probabilidade 0/1
> Para n=2 
> f(1)=2 e f(2)=1. Probabilidade 1/1
> Para n=3 
> f(1)=1, f(2)=3 e f(3)=2, ou
> f(1)=2, f(2)=3 e f(3)=1. Probabilidade 1/2
> Para n=4 
> f(1)=1, f(2)=3, f(3)=4 e f(4)=2, ou
> f(1)=2, f(2)=3, f(3)=4 e f(4)=1, ou
> f(1)=2, f(2)=1, f(3)=4 e f(4)=3. Probabilidade 2/3
> Para n=5 
> f(1)=1, f(2)=3, f(3)=2, f(4)=5 e f(5)=4, ou
> f(1)=1, f(2)=3, f(3)=4, f(4)=5 e f(5)=2, ou
> f(1)=2, f(2)=3, f(3)=4, f(4)=5 e f(5)=1, ou
> f(1)=2, f(2)=1, f(3)=4, f(4)=5 e f(5)=3, ou
> f(1)=2, f(2)=3, f(3)=1, f(4)=5 e f(5)=4. Probabilidade 3/5
> 
> Caso esse problema já tenha sido resolvido na lista e/ou minha solução
> esteja completamente errada, me avisem.
> Gostaria de pedir também se alguém tem dicas sobre bons sites na internet
> que tratem sobre a razão áurea e a sequência de Fibonacci , além de bons
> arquivos que alguém possa
> querer me enviar além de bons exercícios. Meu e-mail é
> plataoterra@ig.com.br.
> 
> grato, 
> 
> Platão Gonçalves Terra Neto
> 


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