On Mon, Jul 02, 2007 at 03:53:32PM -0300, Rogerio Ponce wrote: > 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?
Gostei muito deste problema. A probabilidade de que a moeda seja encontrada é 1 - phi^(-4) = (-5 + 3 sqrt(5))/2 ~= 0.854101966 onde phi = (1+sqrt(5))/2. Acho que é melhor começar considerando um problema relacionado. Suponha que no tempo 0 o primo encontra-se no degrau k > 0. Seja a_k a probabilidade de que o primo *não* volte a pisar no degrau 0. Vamos calcular a_k. Podemos considerar que a_0 = 0. Por teoremas de probabilidade (lei dos grandes números, teorema central do limite ou algo do gênero) sabemos que lim_(k -> + infinito) a_k = 1. Considerando o primeiro pulo, temos ainda a_k = (a_(k-1) + a_(k+2))/2 para k > 0. Para resolver esta equação de diferenças considere a equação l^3 - 2 l + 1 = 0, que tem raízes 1, phi^(-1) ~= 0.6 e -phi ~= -1.6. Assim a_k = C_1 + C_2 phi^(-k) + C_3 (-phi)^k. Pelas condições acima temos C_3 = 0 donde a_k = 1 - phi^(-k). Em particular a_1 = 1 - phi^(-1) = phi^(-2) ~= 0.4. Outro problema preliminar relacionado: no tempo t = 0 o primo está na posição k < 0. Seja b_k a probabilidade de que o primeiro degrau >= 0 a ser pisado seja o degrau 0. Note que ele atingirá degraus >= 0 com probabilidade 1 e que o primeiro a ser pisado pode ser o degrau 0 ou o degrau 1. Vamos calcular b_k. Podemos considerar que b_0 = 1, b_1 = 0. Temos ainda 0 <= b_k <= 1 para todo k < 0. Novamente considerando o primeiro pulo temos b_k = (b_(k-1) + b_(k+2))/2 para k < 0. Novamente temos b_k = C_4 + C_5 phi^(-k) + C_6 (-phi)^k. Pelas condições acima temos C_5 = 0 donde b_k = phi^(-1) + (-phi)^(k-2). Em particular lim_(k -> - infinito) b_k = phi^(-1) ~= 0.6. Vamos agora considerar o problema original. Suponha sem perda de generalidade que a moeda caiu no degrau 0. É melhor calcular a probabilidade de que o primo *não* encontre a moeda, ou seja, de que ele nunca pise no degrau 0. Vamos observar o primeiro instante em que o primo pisa em degraus >= 0. Pelo que vimos sobre b_k (lim_(k -> - infinito) b_k = phi^(-1)), com probabilidade phi^(-1) ele pisa no 0 e acha a moeda; com probabilidade phi^(-2) ele pisa no 1 e não acha a moeda ainda. Para que ele de fato nunca encontre a moeda deve ocorrer o segundo caso e o primo a partir do degrau 1 não deve voltar a pisar no degrau 0. Pelo que vimos sobre a_k (a_1 = phi^(-2)), isto ocorre com probabilidade phi^(-2) e portanto a probabilidade de que a moeda não seja encontrada é phi^(-4). []s, N. ========================================================================= 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 =========================================================================
