Re: [obm-l] Combinat�ria

[Will <will@xxxxxxxxxx>]

Lancando 4 dados justos com valores entre 1 e 9, o valor mais provavel no lancamento 
eh 20.

Como 18 estah mais proximo de 20 do que o 27...

Will


C�pia Faelccmm@aol.com:

> Ok !
> 
> Falando novamente sobre o assunto, vejam as equa��es:
> 
> (I): x1 + x2 + x3 + x4 = 27 (o maior valor para inc�gnitas � 9 e todos
> os 
> valores s�o naturais)
> (II): x1 + x2 + x3 + x4 = 18 (o maior valor para inc�gnitas � 9 e todos
> os 
> valores s�o naturais)
> 
> H� como provar que a equa��o (II) possui mais solu��es que (I) sem 
> resolv�-las pelo m�todo exposto por voc� ?
> 
> Da para generalizar este problema, ou seja, comparar 2 equa��es destes
> tipos 
> (com cotas superior) e dizer qual a que possui mais solu��es ?
> 
> 
> 
> 
> Em uma mensagem de 29/9/2004 14:44:33 Hora padr�o leste da Am. Sul, 
> nicolau@mat.puc-rio.br escreveu:
> 
> 
> > 
> > On Tue, Sep 28, 2004 at 01:54:07PM -0300, Nicolau C. Saldanha wrote:
> > > > Voc�s conhecem a f�rmula para resolver
> > > > 
> > > > x[1] + x[2] + x[3] + ... + x[n] = k, em que 
> > > > 
> > > > 0 =< x[1] , x[2] , x[3] , ... , x[n] =< a (a < k) ?
> > > > 
> > > > Um exemplo do caso geral acima :
> > > > 
> > > > Resolva x + y + w + z = 27 sendo que o maior valor que as
> inc�gnitas 
> > podem 
> > > > assumir seja 9, ou seja, 
> > > > 0 =< x, y, w, z =< 9
> > > 
> > > Eu acho que a pergunta n�o est� muito bem formulada. Eu adivinho que
> voc�
> > > quer saber *quantas* solu��es *inteiras* a equa��o tem. � isso? Se
> for,
> > > n�o � dif�cil.
> > > 
> > > O n�mero de solu��es de x1 + x2 + ... + xn = k, xi >= 0 �
> binom(k+n-1,n-1).
> > > Agora � s� fazer inclus�o e exclus�o: o n�mero de solu��es de
> > > x1 + x2 + ... + xn = k, xi >= 0, x1 >= b � binom(k-b+n-1,n-1):
> > > basta fazer y1 = x1 - b e considerar o problema y1 + x2 + ... + xn =
> k - b.
> > > Assim, para calcular o n�mero de solu��es com 0 <= xi < b precisamos
> tirar 
> > > fora estas solu��es, com o cuidado usual do somar de volta o que for
> 
> > exclu�do
> > > duas vezes e assim por diante:
> > > binom(k+n-1,n-1) - n*binom(k-b+n-1,n-1) +
> binom(n,2)*binom(k-2b+n-1,n-1) 
> > -...
> > > = Soma_{i >= 0} (-1)^i binom(n,i) binom(k - i*b + n - 1, n - 1)
> > 
> > O que eu fiz est� incompleto: faltou especificar o valor m�ximo de
> i.
> > � bem claro pelo racioc�nio que devemos ter k - i*b >= 0.
> > Se definirmos binom(x,y) da forma usual como um polin�mio em x
> > de grau y para cada valor fixo de y ent�o a soma completa d� zero,
> > como podemos facilmente provar.
> > Assim, a resposta �
> > Soma_{i >= 0, i <= k/b} (-1)^i binom(n,i) binom(k - i*b + n - 1, n -
> 1)
> > ou
> > - Soma_{i >= 0, i > k/b} (-1)^i binom(n,i) binom(k - i*b + n - 1, n -
> 1)
> > Outra maneira de obter a segunda f�rmula � observar que o n�mero
> > de soluc�es para k � igual ao n�mero de soluc�es para n*(b-1) - k.
> > 
> > No problema proposto com n = 4, k = 27, b = 10 a resposta �
> > binom(27+4-1,4-1) - 4*binom(27-10+4-1,4-1) + 6*binom(27-2*10+4-1,4-1)
> =
> > binom(30,3) - 4*binom(20,3) + 6*binom(10,3) =
> > 4060 - 4*1140 + 6*120 = 220.
> > 
> > Observem que a segunda f�rmula permite chegar � resposta mais
> rapidamente:
> > 4*binom(0,3) - binom(-10,3) = 4*0 + 220 = 220.
> > 
> > Isto pode ser confirmado procurando o coeficiente de x^27 (ou de
> x^9)
> > em ((x^10-1)/(x-1))^4 =
> > 
> > 36      35       34       33       32       31       30        29     
>   28
> > x   + 4 x   + 10 x   + 20 x   + 35 x   + 56 x   + 84 x   + 120 x   +
> 165 x
> > 
> >             27        26        25        24        23        22      
>  21
> >      + 220 x   + 282 x   + 348 x   + 415 x   + 480 x   + 540 x   + 592
> x
> > 
> >             20        19        18        17        16        15      
>  14
> >      + 633 x   + 660 x   + 670 x   + 660 x   + 633 x   + 592 x   + 540
> x
> > 
> >             13        12        11        10        9        8       
> 7
> >      + 480 x   + 415 x   + 348 x   + 282 x   + 220 x  + 165 x  + 120
> x
> > 
> >            6       5       4       3       2
> >      + 84 x  + 56 x  + 35 x  + 20 x  + 10 x  + 4 x + 1
> > 
> > 
> > []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
=========================================================================