Re: [obm-l] COMBINATÓRIA

[Rafael <rfa1989@xxxxxxxxx>]

Graciliano, vi agora que na minha mensagem anterior confundi uma notacao.
Durante todo o exercicio eu analisei ele em mod3 e nunca em outro mod,
pois estava interessado nos restos da divisao por 3.
Aonde tem escrito mod0, mod1,mod2 era para ser na verdade "congruente
0mod3;  congruente 1mod3; congruente2 mod3".
Depois dessa mancada vou dormir, hehehe.

On 6/2/07, Rafael <rfa1989@gmail.com> wrote:
> Boa noite. Consegui chegar em algum lugar no primeiro. Se voce tiver
> as respostas gostaria de saber se esta certo.
>
> 1)
> Tentei esse exercicio analisando os elementos do conjunto em modulo3.
> Um calculo rapido envolvendo progressao aritmetica nos diz que o
> numero de elementos do conjunto que sao congruentes modulo 0 é:  (150
> - 3)/3 +1 = 50. O numero de elementos congruentes modulo 1 é:
> (148-1)/3 +1 = 50. E o numero de elementos que sao congruentes modulo
> 2 é: (149-2)/3 +1 =50
>
> Agora quais sao as possibilidades de somarmos esse numero para dar um
> multiplo de 3:
> Podemos escolher 3 numeros mod0 para somar OU 3 numeros mod1 OU entao
> 3 numeros mod2.
> Tambem podemos escolher 1numero mod0 E 1numero mod1 E 1numero mod2.
> Nenhum outro tipo de escolha vai nos dar um numero multiplo de 3(por
> exemplo se tivessemos escolhido dois numeros mod0, o terceiro
> obrigatoriamente tem que ser mod0)
>
> A solucao geral , seja para numeros distintos ou nao vai ter essa cara:
> (maneiras de escolher 3numeros mod0) + (maneiras de escolher 3numeros
> mod1) + (maneiras de escolher 3numeros mod0) + [(maneiras de escolher
> 1numero mod0) * (maneiras de escolher 1numero mod1) * (maneiras de
> escolher 1numero mod2)]
>
> Se forem distintos:
> 	C_50,3 + C_50,3 + C_50,3 + [C_50,1 * C_50,1 * C_50,1] = 183800
>
> Se nao forem distintos ficou mais dificil. Tentei usar aquela tecnica
> de transformar em numero de solucoes de uma equacao, espero que o
> raciocinio esteja certo :) .
>
> Do conjunto dos 50 numeros que sao mod0 queremos escolher 3, sendo que
> esses tres podem repetir uma ou mais de uma vez e a ordem de escolha
> deles nao importa. A equacao que poderia representar  isso é   X_1 +
> X_2+...+X_49 + X_50 =3 , pois cada X_i representa o numero de vezes
> que escolhemos o i-esimo elemento do conjunto de 50 numeros. Por
> exemplo escolher 2 vezes o 7ºelemento e uma vez o 50º elemento seria
> uma possivel solucao para a equacao e para o problema pois
> 0+0+0+0+0+0+2+0+...+0+1 =3 e assim vai para todas as escolhas
> diferentes.
>
> O numero de solucoes nao-negativas dessa equacao é 52!/(49!*3!) = 22100
> Analogamente o numero de maneiras de escolher 3 numeros dentre os
> 50numeros mod1 ou dentre os 50numeros mod2 tambem é 22100.
> O numero de maneiras de escolher 1 numero dentre um conjunto de
> 50numeros é 50 mesmo.
>
> Entao a solucao para o caso de nao necessariamente distintos é:
> 	22100 + 22100 + 22100 + [50*50*50] = 191300
>
>
> --
> -----------------------------
>           RAFAEL
>


-- 
-----------------------------
          RAFAEL

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