Ola' Nicolau,
tambem gostei do problema!
Segue a solucao que encotrei.
(me desculpem os colegas da lista, mas a explicacao detalhada tornou o texto
muito longo)
------ Solucao ------
Queremos a probabilidade de que o sapo ache a moeda, ou seja, a probabilidade
de um degrau ser pisado.
Vamos, primeiramente, calcular a probabilidade de que um degrau nao seja pisado
jamais.
Ao contar o numero de pulos do sapo, podemos dizer que:
(usando "#" para designar "o numero de")
#total_de_pulos =
[1 * #degraus visitados exatamente uma vez] +
[2 * #degraus visitados exatamente duas vezes] +
[3 * #degraus visitados exatamente tres vezes] + ...
Como o sapo gasta, na media, 2 pulos para avancar 1 degrau, entao, dividindo os
dois lados da equacao pelo total de degraus percorridos, temos (no limite):
2 =
[1 * probabilidade de um degrau ser visitado exatamente uma vez] +
[2 * probabilidade de um degrau ser visitado exatamente duas vezes] +
[3 * probabilidade de um degrau ser visitado exatamente tres vezes] +
...
Bem, para que um degrau seja visitado mais de uma vez, alguns "loops" serao
necessarios.
Vamos numerar os degraus, de forma que o degrau de referencia para um loop seja
0, e os degraus 'a frente sejam positivos.
Sabemos que o sapo executa pulos com extensao +2 (para frente) e -1 (para tras)
, ambos com probabilidade 1/2 .
Entao, qual e' a probabilidade do sapo retornar a um dado ponto? (ou seja, qual
a probabilidade de um "loop" ?)
Vamos analisar os 3 tipos possiveis de "loops" :
1) Existe um tipo de "loop" em que o sapo utiliza apenas os degraus 'a frente
(ou degraus positivos) do degrau de referencia (ou degrau zero).
Chamemos esse loop de "loop positivo".
Entao, qual a probabilidade de, partindo do degrau 0, o sapo retornar ao mesmo,
tendo pisado apenas em degraus positivos?
Vamos chama'-la de Pp (Probabilidade de "loop com degraus positivos" ):
Basicamente o sapo pula do degrau "0" para o degrau "2", e depois volta ao
degrau "1" , e finalmente volta ao degrau "0".
Neste percurso ele pode executar loops positivos a partir do degrau 2 e a
partir do degrau 1.
Assim, partindo do degrau "0" (sem perda de generalidade) , existe uma
probabilidade de 1/2 de pular para o degrau "2" .
Entao, o sapo pode novamente executar um numero qualquer de "loops positivos" a
partir deste degrau (antes de voltar ao degrau 1).
Entao ha' uma probabilidade de 1/2 de pular para o degrau 1.
E, novamente, o sapo pode executar uma quantidade qualquer de "loops positivos"
, e, finalmente, ha' uma probabilidade de 1/2 de atingir o degrau 0.
Repare que todos os movimentos que o sapo pode fazer num "loop positivo" se
encaixam no esquema descrito.
Assim,
Pp = 1/2 * (1+Pp+Pp**2+Pp**3+... ) * 1/2 * (1+Pp+Pp**2+Pp**3+...) * 1/2
Pp = 1/8 * 1/(1-Pp)**2
Pp * (1-Pp)**2 = 1/8
Por inspecao , 0.5 e' raiz. Assim, apos decompor a expressao, obtemos
(Pp-0.5) * (Pp - (3+sqrt(5))/4 ) * (Pp - (3-sqrt(5))/4 ) = 0
Sabemos que a probabilidade do primeiro pulo (de "0" a "2") e' 0.5 , de forma
que a probabilidade para completar o loop tem que ser menor que 0.5 .
Assim, Pp = (3-sqrt(5))/4
2) Outra especie de loop e' o "loop negativo", em que o sapo pisa apenas em
degraus negativos.
Vamos chamar de Pn a probabilidade deste loop (Probabilidade de loop com os
degraus negativos):
Basicamente o sapo pula do degrau "0" para o degrau "-1", passando depois ao
degrau "-2" , e finalmente volta ao degrau "0".
Neste percurso ele pode executar loops negativos a partir do degrau -1 e a
partir do degrau -2.
Assim, comecando do degrau "0" (sem perda de generalidade), ha' uma
probabilidade de 1/2 de pular para o degrau "-1" .
Entao o sapo pode executar uma quantidade qualquer de "loops negativos" a
partir deste degrau (antes de passar para o degrau "-2").
Entao ha' uma probabilidade de 1/2 de pular para o degrau "-2".
E, novamente, o sapo pode executar uma quantidade qualquer de "loops negativos"
, e, finalmente , ha' uma probabilidade de 1/2 de atingir o degrau 0.
Repare que todos os movimentos que o sapo pode fazer num "loop negativo" se
encaixam no esquema descrito.
Assim,
Pn = 1/2 * (1+Pn+Pn**2+Pn**3+... ) * 1/2 * (1+Pn+Pn**2+Pn**3+...) * 1/2
Observe que a equacao para Pn e' similar 'a equacao para Pp. Assim, Pn =
(3-sqrt(5))/4
3) O ultimo tipo de loop e' o "loop misto", em que o sapo passeia inicialmente
por degraus negativos, e ( apos pular "por cima" do degrau zero) depois passeia
por degraus positivos, antes de voltar ao degrau zero.
Calculemos a probabilidade "Pm" de um loop misto:
Basicamente o sapo pula do degrau "0" para o degrau "-1", passando depois ao
degrau "+1" , e finalmente volta ao degrau "0".
Neste percurso ele pode executar loops negativos a partir do degrau -1 e loops
positivos a partir do degrau +1.
Comecando do degrau "0" (sem perda de generalidade) , ha' uma probabilidade de
1/2 de pular para o degrau "-1" .
Entao o sapo pode executar uma quantidade qualquer de loops negativos a partir
deste degrau (antes de pular para o degrau +1).
Entao ha' uma probabilidade de 1/2 de pular para o degrau "+1"
E, novamente, o sapo pode executar uma quantidade qualquer de "loops positivos"
a partir do degrau +1 , e, finalmente , ha' uma probabilidade de 1/2 de pular
para o degrau 0.
Repare que todos os movimentos que o sapo pode fazer num "loop misto" se
encaixam no esquema descrito.
Pm = 1/2 * (1+Pn+Pn**2+Pn**3+... ) * 1/2 * (1+Pp+Pp**2+Pp**3+...) * 1/2
Assim, Pm = (3-sqrt(5))/4
Entao, a probabilidade "PL" de executar um loop generico e' PL = Pp+Pn+Pm
= (9-3*sqrt(5))/4
Chamemos de "Probabilidade do degrau virgem", ou simplesmente "Pdv", a
probabilidade de que um degrau jamais seja pisado.
Bem, se um degrau e' visitado K vezes, entao apos a primeira visita, havera'
(K-1) loops genericos (de forma que haja mais K-1 visitas), e nenhum loop a
mais.
Assim, a probabilidade de um degrau ser visitado exatamente K vezes e'
[1-Pdv] * [PL**K-1)] * [1-PL]
Lembrando que
2 =
[1 * probabilidade de um degrau ser visitado exatamente uma vez] +
[2 * probabilidade de um degrau ser visitado exatamente duas vezes] +
[3 * probabilidade de um degrau ser visitado exatamente tres vezes] +
...
vemos que podemos reescrever a equacao como:
2 =
[1 * (1-Pdv) * PL**0 * (1-PL) ] +
[2 * (1-Pdv) * PL**1 * (1-PL) ] +
[3 * (1-Pdv) * PL**2 * (1-PL) ] + ...
ou,
2 = (1-Pdv) * (1-PL) * [ 1*PL**0 + 2*PL**1 + 3*PL**2 +... ]
2 = (1-Pdv) * (1-PL) * [ 1/ (1-PL)**2 ]
2 = (1-Pdv) / (1-PL)
Pdv = 2*PL - 1 = [7-3*sqrt(5)] / 2
Pdv = 3.5 - 1.5 * sqrt(5)
Assim, a probabilidade de que o sapo ache a moeda e'
1-Pdv = 1.5 * sqrt(5) - 2.5 = 0.854102
[]'s
Rogerio Ponce
-------------------------------------------
Rogerio Ponce <[EMAIL PROTECTED]> escreveu: Ola' pessoal,
nesse passeio randomico, o sapo pode pisar mais de uma vez em alguns degraus, e
jamais pisar em outros. Ainda assim, podemos afirmar que o sapo pisara' pelo
menos 1 vez em todos os grupos de 2 degraus consecutivos, de modo que a
probabilidade de que ele pise em um degrau qualquer da escadaria (ou seja, a
resposta que estamos procurando) deve ser maior que 0.5 .
[]'s
Rogerio Ponce
PS: dizem que o resultado e' maior que 0.8 ...
Rogerio Ponce <[EMAIL PROTECTED]> escreveu: Ola' pessoal,
Durante o mes de julho, um super-sapo, infinitamente rapido, desceu,
sequencialmente, todos os degraus de uma escadaria infinita. Somente ao final
da viagem ele se deu conta que, ao atender o celular no dia 15, ele deixou cair
sua moeda da sorte em algum degrau.
Entao, pediu a um primo extremamente minucioso, que faria o mesmo percurso
durante o mes de agosto, que ele tentasse encontrar a moeda.
Sabe-se que o primo, ainda mais veloz, desce escadas empregando aleatoriamente
2 tipos de pulos:
- saltos longos para a frente, (quando avanca diretamente do degrau N para o
degrau N+2),
- e saltos curtos para tras (quando retrocede do degrau N para o degrau N-1).
Como os 2 tipos sao equiprovaveis, o primo realmente desce a escadaria, com
taxa media de 1 degrau a cada 2 saltos.
Sabendo-se tambem que seu primo somente examina os degraus em que pisa, qual e'
a probabilidade de que a moeda seja encontrada?
[]'s
Rogerio Ponce
---------------------------------
---------------------------------
Novo Yahoo! Cadê? - Experimente uma nova busca.
