Re: [obm-l] Esperança - Probleminha dificil

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

on 24.03.04 20:06, niski at fabio@niski.com wrote:

> Pensei um tempinho nesse problema e como nao achei nada de muito bom
> resolvi coloca-lo na lista. Alguem sugere uma solucao? Alias, alguem
> sabe se esse livro é de algum livro? Se sim, sabe qual?
> Muito obrigado
> 
> Uma ilha dos mares do sul tem uma floresta antiga de N seringueiras.
> Sabe-se que um pirata famoso escondeu secretamente seu tesouro dentro de
> M (M <= N) dessas arvores, porem nao ha indicacao de quais arvores
> contem ouro. Pensando em achar parte desse tesouro um indiv?duo derruba
> as arvores uma a uma, sendo que elas sao selecionadas ao acaso, e
> verifica se ha ouro dentro de cada uma delas.
> 
> Seja Y o numero de arvores derrubadas ate encontrarem r arvores com
> ouro, r <= M (incluindo as r arvores). Encontre E(Y).

Oi, Niski:

Me parece que o mais razoavel eh considerar duas seringueiras "vazias"
quaisquer como indistinguiveis e duas seringueiras com ouro quaisquer tambem
como indistinguiveis. Em outras palavras, voce soh tem 2 tipos de
seringueira.

Sendo assim, cada "ponto" do seu espaco amostral pode ser representado por
uma N-pla ordenada de 0's e 1's, onde a i-esima coordenada eh 1, se a
i-esima seringueira verificada tem ouro, ou 0, caso contrario.

Para 1 <= k <= N quanto vale P(Y = k)? Ou seja, qual a probabilidade de a
k-esima coordenada de um dado par ser o r-esimo 1 (contando da esquerda pra
direita). 

A k-esima coordenada serah o r-esimo 1 se e somente se, existirem exatamente
r-1 1's dentre as primeiras k-1 cordenadas, o que automaticamente implica a
existencia de M-r 1's dentre as N-k ultimas coordenadas.

De quantas maneiras isso pode acontecer? Eh soh uma questao de colocar os
1's.
Escolha de r-1 coordenadas dentre as primeiras k-1 para colocar os 1's:
Binom(k-1,r-1)
Escolha de M-r coordenadas dentre as ultimas N-k para colocar os demais 1's:
Binom(N-k,M-r)

Total = Binom(k-1,r-1)*Binom(N-k,M-r).

Agora, quantas N-plas ordenadas distintas existem?
Escolha de M coordenadas dentre as N existentes para colocar os 1's:
Binom(N,M)

Logo, temos que P(Y = k) = Binom(k-1,r-1)*Binom(N-k,M-r)/Binom(N,M)

Eh claro que se k < r ou  k > N-M+r, teremos P(Y = k) = 0.

O valor esperado de Y eh igual a:
SOMA(r <= k <= N-M+r) k*P(Y = k) =
SOMA(r <= k <= N-M+r) k*Binom(k-1,r-1)*Binom(N-k,M-r)/Binom(N,M) =
(r/Binom(N,M)) * SOMA(r <= k <= N-M+r) Binom(k,r)*Binom(N-k,M-r).

Essa ultima soma pode ser calculada resolvendo-se de duas maneiras distintas
o problema a seguir:
Temos uma (N+1)-pla ordenada que queremos preencher com 0's e 1's, de forma
que ela contenha exatamente M+1 1's.

Naturalmente, podemos preenche-la de exatamente Binom(N+1,M+1) maneiras
distintas.

Uma outra maneira de contar seria separar em casos da seguinte forma:
Para cada k (r <= k <= N-M+r) colocamos:
a) exatamente r 1's dentre as primeiras k coordenadas;
b) 1 na (k+1)-esima coordenada;
c) (M+1)-(r+1) = M-r 1's dentre as ultimas (N+1)-(k+1) = N-k coordenadas.
Isso pode ser feito de:
SOMA(r <= k <= N-M+r) Binom(k,r)*Binom(N-k,M-r) maneiras distintas.

Logo, concluimos que a soma eh igual a Binom(N+1,M+1) e, portanto, que o
valor esperado de Y eh igual a (r/Binom(N,M))*Binom(N+1,M+1). Ou seja:

E[Y] = r*(N+1)/(M+1).

Eh claro que, depois de ver esta resposta - tao bonitinha - eu estou
convencido de que este problema tem uma solucao em 2 linhas...


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