on 24.03.04 20:06, niski at [EMAIL PROTECTED] 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 =========================================================================
