[obm-l] Re: [obm-l] Dados e equações

["Nicolau C. Saldanha" <nicolau@xxxxxxxxxxxxxx>]

On Fri, Jan 16, 2004 at 01:32:45PM -0300, Erasmo de Souza Dias wrote:
> Tenho um problema não muito simples (pelo menos p/ mim...). E aí vai:
> Lançam-se n dados perfeitos. Determine a probabilidade de que a soma
> das faces voltadas p/ cima, ao cair em solo, de um  número k. (n<=k<=6n).

O número total de maneiras é 6^n, você precisa calcular o número de maneiras
de obter a soma k, ou seja, o número de soluções (inteiras) de

x1 + x2 + ... + xn = k, 1 <= x1, x2, ..., xn <= 6.

Vamos primeiro calcular o número de soluções de

x1 + x2 + ... + xn = k, 1 <= x1, x2, ..., xn. (*)

Este problema você deve conhecer, a resposta é binomial(k-1,n-1).
Agora precisamos jogar fora as soluções grandes demais, ou seja

x1 + x2 + ... + xn = k, 1 <= x1, x2, ..., xn, 7 <= xi

para algum i, 1 <= i <= k. Ora, tomando xi' = xi - 6 isto
equivale a contar as soluções de

x1 + x2 + ... + xi' + ... + xn = k - 6, 1 <= x1, x2, ..., xi', ... xn

o que é um problema exatamente análogo a (*), trocando apenas o valor de k,
e tem portanto binomial(k-7,n-1) soluções. Para cada valor de i precisamos
jogar isto fora então nossa estimativa para o número de soluções está em
binomial(k-1,n-1) - n*binomial(k-7,n-1).

Mas esta ainda não é a resposta certa: afinal se existirem duas variáveis
i1 e i2 que são >= 7, esta solução (que não deveria ser contada) entrou uma
vez mas saiu duas vezes! Precisamos contar estas soluções para somá-las
de volta uma vez e acertar a conta (este método que estamos usando chama-se
o método da união e interseção). Para cada par i1, i2 com i1 < i2 podemos
repetir o truque e fazer xi1' = xi1 - 6, xi2' = xi2 - 6 e temos
binomial(k-13,n-1) soluções. Como existem binomial(n,2) pares i1, i2,
nossa estimativa atual é
binomial(k-1,n-1) - n*binomial(k-7,n-1) + binomial(n,2)*binomial(k-13,n-1)
que eu prefiro escrever como

 SOMATÓRIO   (-1)^a binomial(n,a) binomial(k-1-6a,n-1)
0 <= a <= 2

É claro que ainda não acabou: se existirem três variáveis i1, i2, i3 >= 7,
a solução entrou uma vez, saiu três, entrou três e está sendo contada
quando não deveria estar: precisamos tirá-la (uma vez):

 SOMATÓRIO   (-1)^a binomial(n,a) binomial(k-1-6a,n-1)
0 <= a <= 3

Acho que você já adivinhou que para acertar tudo basta fazer

 SOMATÓRIO   (-1)^a binomial(n,a) binomial(k-1-6a,n-1)
  0 <= a 

e a resposta do seu problema é isto aí dividido por 6^n.

===========================================================================

Outra forma de fazer a conta é usar funções geradoras.
Para um dado a função geradora é

f(x) = (1/6) x + (1/6) x^2 + ... + (1/6) x^6 = x(x^6 - 1)/(6(x-1))

O significado disso é o seguinte: o coeficiente de x^k é a probabilidade
de obtermos a resposta k. Para n dados a função geradora é

(f(x))^n = x^n(x^6 - 1)^n/(6^n(x-1)^n)

e o que você quer é o coeficiente de x^k neste polinômio.
Com um pouco de álgebra dá para chegar à mesma fórmula que nós vimos acima.

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