Re: [obm-l] Combinatória - album de figurinhas...

[Rogerio Ponce <rogerioponce-obm@xxxxxxxxxxxx>]

Ola' pessoal,
uma das formas de se resolver seria calcular o resultado atraves da ponderacao do total das figurinhas necessarias para completar o album inteiro, isto e', o somatorio de "k" figurinhas multiplicado pela probabilidade de se completar o album com exatamente "k" figurinhas, quando "k" varia de N ao infinito (para "k" abaixo de N, a probabilidade de se completar o album vale zero).

Portanto a media vale
SOMATORIO k=[N,oo] { k * Prob_completar_album(N,k) }

Entretanto, o calculo de "Prob_completar_album(N,k)", isto e', a probabilidade de se completar um album de N posicoes com exatamente k figurinhas (de um universo de N figurinhas) me pareceu muito enrolado, e acabei tomando um caminho mais simples.

Basta percebermos que a media das figurinhas necessarias para completarmos o album vale o mesmo que a soma das medias das figurinhas necessarias para ocuparmos cada uma das N posicoes do album.

E quanto vale cada uma dessas parcelas?
~

Ora, quando ha' V posicoes vagas num total de N posicoes possiveis, a probabilidade de conseguirmos uma figurinha que se encaixe e' V/N.Isto significa que, na media, a cada N figurinhas compradas, V figurinhas poderiam ser encaixadas nas posicoes vagas (nao necessariamente em vagas distintas!).Dividindo isso por V, significa que, na media, precisamos comprar N/V figurinhas para conseguirmos um encaixe quando houver V posicoes vagas.

Assim, na media, precisaremos comprar:
 N/N figurinhas para conseguirmos colar a 1a. figurinha no album
 N/(N-1) figurinhas para conseguirmos colar a 2a. figurinha no album
e assim sucessivamente, ou seja, na media serao necessarias
 N*[1 + 1/2 + 1/3 + ... + 1/N] figurinhas.

Abracos a todos,
Rogerio Ponce


Carlos Nehab <nehab@infolink.com.br> escreveu:

> Oi, gente,
>
> Considere uma revista de "figurinhas" com N figurinhas distintas. Qual 
> o número médio de figurinhas que se deve comprar para "completar" o 
> álbum? Imaginem que as figurinhas são compradas unitariamente (uma a uma).
>
> Nehab
>
> PS: Quem sabe o Palmerim bota na coleção dele...
>
> =========================================================================
> 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
> =========================================================================

Abra sua conta no Yahoo! Mail, o único sem limite de espaço para armazenamento!