on 26.01.05 13:39, plataoterra at [EMAIL PROTECTED] 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 é
> [EMAIL PROTECTED]
>
> 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
=========================================================================
