Re: [obm-l] COMBINATÓRIA

[Rafael <rfa1989@xxxxxxxxx>]

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

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