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