[obm-l] ajuda

[plataoterra <plataoterra@xxxxxxxxx>]

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

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