Re: [obm-l] um puzzle

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

on 28.04.04 17:14, Domingos Jr. at dopikas@uol.com.br wrote:

> Eu ia colocar "processo estocástico" no subject, mas muita gente ia deixar
> de ler, hehehe, então aí vai:
> 
> Suponha que tenhamos 5 quadrados dispostos em forma de cruz:
> X
> X X X
> X
> 
> Ok, imagine que vc tem um robô cego e sem memória no centro, ele decide, a
> cada  turno, com probabilidade 1/4, ir para uma das direções L, O, N, S.
> Evidentemente, se ele está fora do centro, ele não pode tomar 3 das 4
> direções possíveis, mas mesmo assim, o coitado é cego, tenta e percebe que
> não deu, mas ele não tem memória e pode repetir o mesmo movimento no próximo
> turno.
> 
> A longo prazo, quantos turnos ele passa (proporcionalmente) em cada um dos 5
> quadradinhos?
> 
Estou supondo que os quadradinhos ("O") tem a seguinte disposicao:
.O.
OOO
.O.
(jogo da velha sem os cantos, por exemplo...)

Suponhamos que, num certo turno, ele comeca no centro.
Entao, no turno seguinte ele estarah numa das 4 pontas.

Quanto tempo vai levar pra ele voltar pro centro?
Resposta: 
1 turno, com probabilidade = 1/4;
2 turnos, com probabilidade = 3/4*1/4;
3 turnos, com probabilidade = 3/4*3/4*1/4;
...
n turnos, com probabilidade = (3/4)^(n-1)*1/4;
...

Logo, o valor esperado do tempo eh igual a:
(1/4)*SOMA(n>=1) n*(3/4)^n = 4 turnos.

Uma outra forma de ver isso eh observar que, como o robo nao tem memoria, o
valor esperado do tempo para o retorno ao centro independe de quantos turnos
ele jah passou numa dada ponta. Assim, se o valor esperado do tempo no
inicio do turno k eh E_k e no inicio do turno k+1 eh E_(k+1), entao:
E_(k+1) = E_k

Mas por outro lado, E_k = 1 + (3/4)*E_(k+1).

Logo, E_k = 1 + (3/4)*E_k ==> E_k = 4

Ou seja, em media, ele voltarah ao centro a cada 1+4 = 5 turnos ==>
ele passarah 20% do tempo no centro e 80% nas pontas.
Por simetria, concluimos que ele passarah 20% do tempo em cada uma das 4
pontas, ou seja:
ele passarah 20% do tempo em cada um dos 5 quadradinhos.

[]s,
Claudio.


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