Colecionando Figurinhas - Parte 1

Esse é o primeiro de uma série de dois ou três posts sobre colecionar figurinhas. Eu sei que a outra série que prometi - sobre erros probabilísticos em seriados de TV - só tem uma parte há mais de um ano, mas dessa vez acredito que vamos ter mais de um capítulo! Bom, vamos lá...

Suponha que você tem um álbum com N figurinhas no total. Você já possui X delas e pretende comprar alguns pacotes (os pacotinhos), contendo K figurinhas cada um, possivelmente repetidas. Quantos pacotes em média você vai ter que comprar para conseguir uma figurinha não repetida - a sua figurinha número X+1?

  

Estragando a surpresa

Eu vou falar logo a resposta: N / [K*(N-X)]. Lá em baixo, vou mostrar como se chega a esse resultado. Quem tiver a curiosidade de ler, vai ver que não é tão complicado assim, mas também não é imediato.

O último álbum da Copa até a data deste post, o álbum de 2010, tinha 640 figurinhas. Isso significa que, se você tivesse 639 delas,  teria que comprar em média 640/5 = 128 pacotes. Como cada pacote custava R$0,75 centavos, o mal caráter que queria te vender a última das últimas por, vamos chutar, R$10,00, além de mal caráter não sabia fazer negócio. Essa figurinha te pouparia de gastar cerca de R$96,00.

No próximo post, com o auxílio da fórmula acima, eu vou falar do número esperado de pacotes que alguém teria que comprar para completar o álbum inteiro. Para você não ficar esperando por isso - talvez demore anos! - adianto que o número de pacotes esperados é N*H(N)/K ~ N*ln(N)/K. No caso do álbum da copa, seriam aproximadamente 900 pacotes ou R$675,00.

Por trás dos panos

Para simplificar um pouco o raciocínio, vamos supor que K = 1. Depois, com um argumento bastante simples, veremos que o valor de K é menor de todos os nossos problemas. Sabendo que cada pacote contém apenas uma figurinha, a gente pode se imaginar tirando figurinhas de um bolo de figurinhas (desculpa, mas figurinhas não tem nenhum sinônimo decente) até que saia uma inédita. Outra coisa: vou usar as palavras "comprar" (pacotes) e "tirar" (figurinhas) querendo dizer a mesma coisa, considerando que agora estamos imaginando nossa compra de pacotes como tirar figurinhas de um monte.

Um pouco de notação: seja p(X,i) a chance de tirarmos do monte exatamente i figurinhas até acharmos uma inédita. Isso implica em tirar i-1 figurinhas repetidas e depois 1 que não temos. Como existem X figurinhas que não te interessam mais (as que você já tem) e N-X figurinhas que te interessam (as que você ainda não tem), podemos expressar p(X,i) assim:

Na nossa ansiosa e emocionante busca pela figurinha X+1, podemos dar sorte e tirá-la do monte logo de primeira. Também podemos dar um pouco menos de sorte e tirar por exemplo 5 figurinhas até achar uma que não tínhamos antes. Ou, bem, a gente pode dar muito, mas muito azar e tirar um número arbitrariamente grande de figurinhas antes de terminarmos a nossa busca. Resumindo, existem vários casos, cada um deles com uma chance diferente de acontecer. Os primeiros dois casos que descrevi - com 1 e 5 figurinhas - correspondem a p(X,1) e p(X,5), como você já deve ter imaginado.

Agora eu vou dizer uma coisa que você deve reler até entender bem e achar que faz muito sentido: 

O número médio (ou esperado) de figurinhas que devemos tirar do monte é a soma da quantidade de figurinhas que tiramos em cada caso ponderada pela chance de ocorrência desse caso.

Em outras palavras,

A coisa vai ficar um pouco feia, mas na realidade só vamos reescrever a igualdade acima substituindo p(X,i) pelo outro nome dele.

Até esse momento, a única coisa que fizemos foi traduzir do português para a matemática a nossa afirmação sobre o número esperado de figurinhas que iremos comprar até conseguirmos uma figurinha que não tínhamos. E parece que a gente está em apuros, com uma somatório estranho que tem infinitos termos, frações, produtos, exponenciação... É verdade, tem tudo isso. E você vai ver como esse monstro na verdade não deveria te assustar. O que vamos fazer é uma das coisas belas em matemática: vamos ver que esse problema (resolver esse somatório) na verdade é exatamente um outro problema bem conhecido, que todo mundo que está na oitava série ou no primeiro ano sabe resolver.

A primeira coisa a ser observada é que o termo mais à direita, (N-X)/N é independente do valor de i e por isso pode ser colocado fora do somatório. Portanto,

O nosso problema agora se resumo a resolver o somatório, certo? A segunda coisa a ser observada é que o termo (X/N) é menor do que 1, porque N > X (por quê?). Toda vez que você vir um termo menor do que 1 dentro de um somatório sendo exponenciado, pense em séries geométricas convergentes. Afinal, é isso que elas são: termos menores do que 1 dentro de um somatório sendo exponenciados!

De acordo com o que sabemos sobre séries geométricas, se 0 < a < 1,

Se a gente derivar os dois lados em relação à variável a, temos

Depois de tudo isso, olhe para a última expressão do valor esperado e também para o que acabamos de obter. A conclusão imediata é que nosso problema sobre figurinhas pode ser resumido a resolver uma série geométrica. É muito importante assimilar que só podemos relacionar essas duas fórmulas porque X/N é positivo e menor do que 1, e isso foi tudo que assumimos a respeito da variável a.

Enfim, depois da substituição e algumas simplificações,

É sempre bom verificar se a fórmula faz sentido para valores triviais, como X =  0, que significa que não temos nenhuma figurinha ainda. Nesse caso, o valor esperado é N/N = 1, exatamente o que deveria ser: afinal, a primeira figurinha será certamente uma que não temos. Além disso, vale dizer que X = N não faz sentido - essa é a situação em que já completamos o álbum.

Bem, e o valor de K, afinal? Fica para você pensar: eu não posso dizer que comprar 5 pacotes no caso K = 1 é a mesma coisa que comprar uma pacote no caso K = 5? Lembre-se: os pacotinhos podem ter figurinhas repetidas.