Re: [obm-l] Combinatória

[Claudio Buffara <claudio.buffara@xxxxxxxxxxxx>]

on 16.12.03 22:26, benedito at benedito@digizap.com.br wrote:

> Dois problemas interessantes:
> 1) Encontre o número de triplas ordenadas de conjuntos  (A, B, C) tais que
> a união  AuBuC = {1, 2, 3, ..., 2003} e a interseção dos três conjuntos   A,
> B , C  é vazia.
> 
O enunciado eh de fato A inter B inter C = vazio ou A, B e C sao disjuntos
dois a dois ?

No primeiro caso, a tripla ( {1} , {1,2} , {2,3,...,2003} ) deve ser
incluida, mas no segundo caso nao.

Se A, B e C forem disjuntos dois a dois, entao o numero de triplas eh
3^2003. Isso sai por meio de uma recorrencia facil: F(1) = 3, F(n+1) =
3*F(n), onde F(n) eh o numero de triplas (A,B,C) com A, B e C disjuntos dois
a dois e A U B U C = {1,2,...,n}.

Mas se for apenas A inter B inter C = vazio, o problema fica mais dificil.


> 2) Determine  o número de funções  f  definidas  em  {1, 2, 3, ...., 1999}
> e assumindo valores  em  {0, 1, 2, 3} tais que  a soma  f(1) + f(2) + f(3) +
> ..+ f(1999)  é ímpar.
> 
Uma soma de inteiros eh impar ==> existe um numero impar de parcelas
impares.

Suponha que 2k-1 parcelas sejam impares (1<=k<=1000) e as restantes 2000-2k
sejam pares.
Escolha de 2k-1 numeros do dominio que terao imagem impar: Binom(1999,2k-1)
Escolha do valor da imagem (1 ou 3) para cada um deles: 2^(2k-1)
Escolha do valor da imagem (0 ou 2) para os 2000-2k restantes: 2^(2000-2k)
Total = Binom(1999,2k-1)*2^1999.

Logo, o numero de funcoes serah igual a:
SOMA(1<=k<=1000) Binom(1999,2k-1)*2^1999 =
2^1999 * (Binom(1999,1) + Binom(1999,3) + ... + Binom(1999,1999)) =
2^1999 * 2^1998 = 
2^3997.

Um abraco,
Claudio.


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