[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: [obm-l] COMBINATÓRIA



Nossa! Totalmente errado o que fiz. Não considerei os valores que x, y e z podem assumir (no máximo 150). Desculpas!

On 6/1/07, Henrique Rennó < henrique.renno@gmail.com> wrote:
Olá Graciliano!

Acho que este problema dá pra resolver aparentemente da mesma forma que aquele problema proposto pelo Rafael alguns dias atrás e que você havia mostrado uma solução transformando o problema em uma equação.

1) De quantos modos podemos escolher tres numeros, não necessariamente distintos, no conjunto {1,2,...,150} de modo que a soma dos numeros escolhidos seja divisivel por 3? E se os numeros fossem distintos?

Para que os três números somados seja um valor divisível por 3 a soma deve ser um número do conjunto M = {3, 6, 9, ..., 450}, ou seja, todos os múltiplos de 3 possíveis de serem formados através da soma de elementos do conjunto E = {1, 2, ..., 150} sendo o elemento mínimo 1+ 1+ 1 = 3 e o máximo 150 + 150 + 150 = 450.

O número de escolhas de 3 elementos de E que somados é 3 seria igual ao número de soluções inteiras positivas para a equação x + y + z = 3. Já que o x, y e z são inteiros positivos (tirados de E) existe apenas uma única solução, pois que teríamos que considerar pelo menos uma unidade para x, y e z, ou seja, 1+1+1 = 3 --> 0+0+0 = 0.

O número de possibilidades para que a soma seja 6 seria o número de soluções inteiras positivas para a equação x + y + z = 6. Novamente, cada termo x, y e z possui no mínimo uma unidade, logo o número de soluções para essa equação seria equivalente ao número de permutações com elementos repetidos de III++ (pois retirando três unidades garantimos que x, y e z são >= 1 já que são elementos de E). Então, para a soma ser igual a 6 existem 5!/(3!2!) = 10 possibilidades.

Seguimos o mesmo raciocínio para as somas 9, 12, 15, ..., 450.

9 --> IIIIII++ --> 6 unidades --> 8!/(6!2!) = 28
12 --> IIIIIIIII++ --> 9 unidades --> 11!/(9!2!) = 55
etc

Então o resultado final seria 2!/(0!2!) + 5!/(3!2!) + 8!/(6!2!) + 11!/(9!2!) + ... + 449!/(447!2!) = 1 + 10 + 28 + 55 + ... + 100576 = 1 + (1 + 1*9) + (1 + 1*9 + 2*9) + (1 + 1*9 + 2*9 + 3*9) + ... + (1 + 1*9 + 2*9 + 3*9 + ... + 149*9) = 150*1 + 149*1*9 + 148*2*9 + 147*3*9 + ... + 3*147*9 + 2*148*9 + 1*149*9 = 150 + 2*149*1*9 + 2*148*2*9 + 2*147*3*9 + ... + 75*75*9 = 150 + 75*75*9 + 2*9*(149*1 + 148*2 + 147*3 + ... + 76*74) = não sei como continuar....

O resultado poderia ser representado como S(n=2,3,449){n!/[(n-2)!2!]}, ou seja, o somatório de n = 2 a 449 com passo 3 de n!/[(n-2)!2!].

Acho que a resolução deva estar correta. Estou em dúvidas com relação ao caso de serem escolhidos elementos distintos para a soma.

Bom fim de semana!

--
Henrique



--
Henrique